Как найти число без куба

Cube-free numbers are those numbers that have no cubic divisors.

A cubic divisor refers to an integer that is a cube and divides the number with zero remainders.

For example, 8 is a cubic divisor of 16 since 8 is a cube of 2 (2*2*2 = 8), and 8 divides 16 with the remainder of zero.

Thus, 8 and 16 both are not cube-free numbers.

Problem Statement

Find all the cube-free numbers less than a given number, n.

Example

Let's understand the problem with an example.
Let n = 15,
Thus, we have to find all the numbers less than 15 that are cube-free.
The solution will be:  2,3,4,5,6,7,9,10,11,12,13,14.
For another example,
Let n = 20.
The numbers are 2,3,4,5,6,7,9,10,11,12,13,14,15,17,18,19.

Explanation

Notice that 1, 8, and 16 are not on the list. Because 1 and 8 are cubic numbers in themselves and 16 is the multiple of 8.

There are two approaches to this problem.

Approach 1: Brute Force Approach

The brute force approach is as follows −

• Traverse through all the numbers till n.

• For each number, traverse through all of its divisors.

• If any divisor of the number is a cube, then the number is not cube-free.

• Else, if none of the divisors of the numbers is a cube, then it is a cube-free number.

• Print the number.

Example

The program for this approach is as follows −

Below is a C++ program to print all the cube free numbers less than a given number n.

#include<iostream>
using namespace std;
// This function returns true if the number is cube free.
// Else it returns false.
bool is_cube_free(int n){
   if(n==1){
      return false;
   }
   //Traverse through all the cubes lesser than n
   for(int i=2;i*i*i<=n ;i++){
      //If a cube divides n completely, then return false.
      if(n%(i*i*i) == 0){
         return false;
      }
   }
   return true;
}
int main(){
   int n = 17;
   cout<<"The cube free numbers smaller than 17 are:"<<endl;
   //Traverse all the numbers less than n
   for(int i=1;i<n;i++){
      //If the number is cube free, then print it.
      if(is_cube_free(i)){
         cout<<i<<" ";
      }
   }
}

Output

The cube free numbers smaller than 17 are:
2 3 4 5 6 7 9 10 11 12 13 14 15

Approach 2: Sieve of Eratosthenes Technique

An efficient solution for this problem will be the concept of the Sieve of Eratosthenes.

It is used to find the prime numbers up to a given limit. Here, we will sieve out the numbers that aren’t cube-free to get our solution.

The approach is as follows −

• Create a boolean list of size n.

• Mark all the numbers as true. It means that we have marked all the numbers as cube-free for now.

• Traverse through all the possible cubes less than n.

• Traverse through all the multiples of the cubes less than n.

• Mark all those multiples as false in the list. These numbers are not cube free.

• Traverse through the list. Print the numbers in the list which are still true.

• The output will consist of all the cube-free numbers less than n.

Example

The program for this approach is as follows −

Below is a C++ Program to print all the cube free numbers less than a given number n with Sieve of Eratosthenes approach.

#include<iostream>
#include<vector>
using namespace std;

//Find which numbers are cube free and mark others as false in the vector.
void find_cube_free(vector<bool>&v, int n){
   //Traverse through all the numbers whose cubes are lesser than n
   for(int i=2;i*i*i<n;i++){
      
      //If i isn't cube free, it's multiples would have been marked false too
      if(v[i]==true){
         //Mark all the multiples of the cube of i as not cube free.
         for(int j=1;i*i*i*j<n;j++){
            v[i*i*i*j] = false;
         }
      }
   }
}
int main(){
   int n = 15;
   
   //Vector to store which numbers are cube free
   //Initially, we set all the numbers as cube free
   vector<bool>v(n,true);
   find_cube_free(v,n);
   cout<<"The cube free numbers smaller than are:"<<endl;
   
   //Traverse the vector and print the cube free numbers
   for(int i=2;i<n;i++){
      if(v[i]==true){
         cout<<i<<" ";
      }
   }
}

Output

The cube free numbers smaller than are:
2 3 4 5 6 7 9 10 11 12 13 14

This article solved the problem of finding cube free numbers less than n. We saw two approaches: a brute force approach, and an efficient one using the Sieve of Eratosthenes technique.

C++ programs are provided for both of the approaches.

Как-то раз британскому министру образования в телеинтервью 10-летняя девочка задала вопрос: “назовите кубический корень из 125”. Министр не ответила и сказала, что не будет отвечать ни на какие вопросы, связанные с математикой.

С одной стороны её можно понять. А с другой стороны, знай она простое правило, о котором я сегодня расскажу, она бы не попала в такую ситуацию. Впрочем, многие небезосновательно считают, что не знать кубический корень из 125 просто стыдно.

Итак, чтобы считать кубические корни, мы должны знать кубики (так я называю число в кубе) чисел от 1 до 10. Большинство их и так знает. И сразу обратим внимание на то, какой цифрой они заканчиваются.

Тут надо заметить интересную вещь. Куб чисел 1, 4, 5, 6, 9 и 0 или 10 заканчивается на само число. А числа 2 и 8 и 3 и 7 следует запоминать парами. То есть куб двойки заканчивается на 8, а куб восьмерки — на 2. И с 3 и 7 то же самое: куб тройки заканчивается на 7, а куб семерки — на 3.

Давайте извлечём кубический корень из числа 39 304

Шаг первый

Смотрим, на что оканчивается число 39304? На цифру 4. Это соответствует четверке (смотри табличку выше). Запоминаем эту цифру или где-то записываем (это будет последний цифрой в искомом числе).

Шаг второй

Теперь проигнорируем последние 3 цифры нашего числа и найдем ближайший к этому числу куб, не превосходящий его.

Игнорируем три последние цифры — 39304. Осталось 39. Это число располагается между 27=3³ и 64=4³. Но так как нам нужен куб, не превосходящий число, то нас устраивает только 27. Это куб трёх. Поэтому второй цифрой, которую мы запоминаем (или записываем) будет тройка. Пишем её левее четверки и получаем число 34.

На самом деле всё, потому что 34³=39304. Легко и просто!

Теперь извлечем кубический корень из числа 636 056

Шаг первый

Число заканчивается на 6. Это соответствует шестерке, так как 6³=256. Запоминаем шестерку.

Шаг второй

Зачеркиваем три последние цифры и смотрим на оставшиеся три. 636 056 -> 636. Ближайший к этому числу куб, не превосходящий его — 512. Следующий куб —729, он уже больше 636.

512=8³, поэтому второе число, которое мы должны запомнить — 8. Объединяем оба числа и получаем 86. И в самом деле 86³=636056.

Где это пригодится?

Например, чтобы провести математический фокус. Попросите друга загадать какое-то двухзначное число про себя и никому его не говорить. Теперь пусть он возведет его в куб и скажет вам результат. А вы спустя пару секунд назовете ему загаданное им число. Уверен, что у вас это получится сделать в уме гораздо быстрее, чем он будет дважды умножать число само на себя столбиком на листочке.

Ещё это может пригодиться, чтобы удивить учительницу. Ну или для того, чтобы сэкономить время на ЕГЭ. Хотя последнее очень сомнительно. В школе не учат извлекать кубические корни в уме, поэтому и заданий там таких нет.

Не забывайте подписываться на мои каналы в Ютубе, Инстаграме и ТикТоке. И, конечно, буду рад, если вы поставите лайк и напишете в комментариях, знали ли вы о таком способе или нет. А если поделитесь публикацией в своих соцсетях, то сильно поможете моему каналу стать популярнее.

Ещё интересно: Не игра в кальмара, конечно, но тоже сложная южнокорейская головоломка

На самом деле всё просто: как переводить из десятеричной системы в двоичную и наоборот

Американский метод решения уравнений. Никакой путаницы со знаками не будет

30.12.2019Математика

Input :  n = 10
Output : 2 3 4 5 6 7 9 10
Note that only 1 and 8 are missing. 

Input : 20
Output : 2 3 4 5 6 7 9 10 11 12 13 14 
         15 17 18 19 20 

2 3 4 5 6 7 9 10 11 12 13 14 15 17 18 19 20

2 3 4 5 6 7 9 10 11 12 13 14 15 17 18 19 20

Для начала извлечь его хотя бы “с точностью до 10”. То есть разделить число на 1000, если оно большое, и прикинуть, к кубу какого простенького числа (от 1 до 10) ближе всего результат. Ну или между кубами каких двух чисел. Уж кубы от 1 до 9 сосчитать в уме не штука (ваще-то можно и помнить).

Ну а дальше просто воспользоваться приближённой формулой (а+х)³ ≈ а³ + 3а²х. То есть надо сосчитать разность между кубом “простого числа” и исходным числом, поделить её на 3, на квадрат найденного “простого” основания и прибавить к найденному простому числу.

Ну пусть надо извлечь корень из 123456. Это меньше миллиона, так что кубический корень явно меньше 100. Делим на 1000, чтоб было проще, получаем круглым счётом 123. Ближайший куб – это 125 (5*5*5). От исходного числа (123,456) это отличается на 1,544. Делим -1,544 на 25 и на 3 – получаем примерно -0,021 (это не тире, это знаки “минус”). Это надо прибавить к выбранному основанию – получается 4,979. Значит, исходный корень равен 49,79.

А теперь проверяем: 49,79³ ≈ 123432. Вполне достаточная точность.

  Кубический корень. Как извлечь квадратный корень из большого числа без калькулятора мы уже разобрали. В этой статье рассмотрим как извлечь кубический корень (корень третьей степени). Оговорюсь, что речь идёт о натуральных числах. Как вы думаете, сколько времени нужно, чтобы устно вычислить такие корни как:

Совсем немного, а если потренируетесь  два-три раза минут по 20, то любой такой корень вы сможете извлечь за 5 секунд устно.

*Нужно отметить, что речь идёт о таких числах стоящих под корнем, которые являются результатом возведения в куб натуральных чисел от 0 до 100.

Мы знаем, что:

Так вот, число а, которое мы будем находить – это натуральное число от 0 до 100. Посмотрите на таблицу кубов этих чисел (результаты возведения в третью степень):

Вы без труда  сможете извлечь кубический корень из любого числа в этой таблице. Что нужно знать?

1. Это кубы чисел кратных десяти:

Я бы даже сказал, что это «красивые» числа, запоминаются они легко. Выучить несложно.

2. Это свойство чисел при произведении.  

Его суть заключается в том, что при возведении в третью степень какого-либо определённого числа, результат будет иметь особенность. Какую?

Например, возведём в куб 1, 11, 21, 31, 41 и т.д. Можно посмотреть по таблице.

1³ = 1,   11³ = 1331,   21³ = 9261,   31³ = 26791,   41³ = 68921   …

То есть, при возведении в куб числа с единицей на конце в результате  у нас всегда получится число с единицей в конце.

При возведении в куб числа с двойкой на конце в результате всегда получится число с восьмёркой в конце.

Покажем соответствие в табличке для всех чисел:

Знания представленных двух моментов вполне достаточно.

Рассмотрим примеры:

Извлечь кубический корень из 21952.

Данное число находится в пределах от 8000 до 27000. Это означает, что результат корня лежит в пределах от 20 до 30. Число 29952 заканчивается на 2. Такой вариант возможен только тогда, когда в куб возводится число с восьмёркой в конце. Таким образом, результат корня равен 28.

Извлечь кубический корень из 54852.

Данное число находится в пределах от 27000 до 64000. Это значит, что результат корня лежит в пределах от 30 до 40. Число 54852 заканчивается на 2. Такой вариант возможен только тогда, когда в куб возводится число с восьмёркой в конце. Таким образом, результат корня равен 38.

Извлечь кубический корень из 571787.

Данное число находится в пределах от 512000 до 729000. Это значит, что результат корня лежит в пределах от 80 до 90. Число 571787 заканчивается на 7. Такой вариант возможен только тогда, когда в куб возводится число с тройкой в конце. Таким образом, результат корня равен 83.

Извлечь кубический корень из 614125.

Данное число находится в пределах от 512000 до 729000. Это значит, что результат корня лежит в пределах от 80 до 90. Число 614125 заканчивается на 5. Такой вариант возможен только тогда, когда в куб возводится число с пятёркой в конце. Таким образом, результат корня равен 85.

Думаю, что вы теперь без труда сможете извлечь кубический корень из числа 681472.

Конечно, чтобы извлекать такие корни устно, нужна небольшая практика. Но восстановив две указанные таблички на бумаге, вы без труда в течение минуты, в любом случае, такой корень извлечь сможете.

После того, как нашли результат обязательно сделайте проверку (возведите его с третью степень). *Умножение столбиком никто не отменял 😉

На самом ЕГЭ задач с такими «страшненькими» корнями  нет. Например, в Задаче 27125 требуется извлечь кубический корень из 1728. Думаю, что это теперь для вас не проблема.

Если вы знаете какие-то интересные приёмы вычислений без калькулятора, присылайте, со временем опубликую. На этом всё. Успеха Вам!

С уважением, Александр Крутицких. 

P.S: Буду благодарен Вам, если расскажете о сайте в социальных сетях.