Cube Free Numbers smaller than n

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.