cubic free number less than n

Numbers without cubic factors refers to those numbers that do not have cubic numbers as factors.

A cubic number factor is an integer that is a cubic number and can divide the number without a remainder.

For example, 8 is a cube factor of 16 because 8 is a cube factor of 2 (2*2*2 = 8), and the remainder when dividing 8 by 16 is zero.

Therefore, neither 8 nor 16 are cubeless numbers.

Problem Statement

Find all cubeless numbers less than the given number n.

The translation of

Example

is:

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.

The Chinese translation of

Explanation

is:

Explanation

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

There are two ways to solve this problem.

Method One: Violence Method

The method of brute force cracking is as follows:

• Traverse through all numbers until n.

• For each number, iterate through all its divisors.

• If any factor of a number is a cube, then the number is not cubeless.

• Otherwise, if none of the divisors of these numbers are cubic, then it is a cubeless number.

• Print numbers.

The translation of

Example

is:

Example

The program for this approach is as follows −

The following is a C program to print all cubeless 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

Method 2: Sieve of Eratosthenes technique

A highly efficient way to solve this problem would be the concept of the Sieve of Eratosthenes.

It is used to find prime numbers smaller than a given limit. Here we will filter out the numbers that are not cubic numbers to get our solution.

The method is as follows −

• Create a boolean list of size n.

• Mark all numbers as true. This means that we have currently labeled all numbers as cubeless.

• Traverse all possible cubes less than n.

• Traverse all multiples of cubic numbers less than n.

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

• Traverse the list. Print the numbers in the list that are still true.

• The output will include all cubeless numbers less than n.

The translation of

Example

is:

Example

The program for this approach is as follows −

The following is a C program that uses the sieve of Eratosthenes to print all cubeless numbers less than a given number n.

#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 solves the problem of finding cubeless numbers less than n. We saw two methods: a brute force method and an efficient method using the sieve of Eratosthenes.

C program provides implementation of these two methods.

The above is the detailed content of cubic free number less than n. For more information, please follow other related articles on the PHP Chinese website!