A cube free number square free number whose none of any divisor is a cubic number (a number which is cube of an integer). Given an integer n, find all cube free numbers smaller than or equal to n.
Examples :
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
A simple solution is to traverse through all numbers from 1 to n. For every number check if it is cube free or not. If yes, then print it.
C++
// Simple C++ Program to print all cube free// numbers smaller than or equal to n.#include <bits/stdc++.h>using namespace std;// Returns true if n is a cube free// number, else returns false.bool isCubeFree(int n){ if (n == 1) return false; // check for all possible divisible cubes for (int i = 2; i * i * i <= n; i++) if (n % (i * i * i) == 0) return false; return true;}// Print all cube free numbers smaller// than n.void printCubeFree(int n){ for (int i = 2; i <= n; i++) if (isCubeFree(i)) cout << i << " ";}/* Driver program to test above function */int main(){ int n = 20; printCubeFree(n); return 0;} |
Java
// Java Program to print all cube free// numbers smaller than or equal to n.class GFG{ // Returns true if n is a cube free // number, else returns false. public static boolean isCubeFree(int n) { if (n == 1) return false; // check for all possible divisible cubes for (int i = 2; i * i * i <= n; i++) if (n % (i * i * i) == 0) return false; return true; } // Print all cube free numbers smaller // than n. public static void printCubeFree(int n) { for (int i = 2; i <= n; i++) { if (isCubeFree(i)) { System.out.print ( i + " "); } } } // Driver program public static void main(String[] args) { int n = 20; printCubeFree(n); }}// Contributed by _omg |
Python3
# Python3 Program to print all cube free# numbers smaller than or equal to n.import math # Returns true if n is a cube free# number, else returns false.def isCubeFree( n ): if n == 1: return False # check for all possible divisible cubes for i in range(2, int(n ** (1 / 3) + 1)): if (n % (i * i * i) == 0): return False; return True; # Print all cube free numbers smaller# than n. def printCubeFree( n ): for i in range(2, n+1): if (isCubeFree(i)): print ( i , end= " ") n = 20printCubeFree(n)# Contributed by _omg |
C#
// C# Program to print all cube free// numbers smaller than or equal to n.using System;class GFG{ // Returns true if n is a cube free // number, else returns false. static bool isCubeFree(int n) { if (n == 1) return false; // check for all possible divisible cubes for (int i = 2; i * i * i <= n; i++) if (n % (i * i * i) == 0) return false; return true; } // Print all cube free numbers smaller // than n. static void printCubeFree(int n) { for (int i = 2; i <= n; i++) { if (isCubeFree(i)) { Console.Write ( i + " "); } } } public static void Main() { int n = 20; printCubeFree(n); }}// Contributed by _omg |
PHP
<?php// Simple PHP Program to // print all cube free // numbers smaller than // or equal to n.// Returns true if n is // a cube free number, // else returns false.function isCubeFree($n){ if ($n == 1) return false; // check for all possible // divisible cubes for ($i = 2; $i * $i * $i <= $n; $i++) if ($n % ($i * $i * $i) == 0) return false; return true;}// Print all cube free // numbers smaller than n.function printCubeFree($n){ for ($i = 2; $i <= $n; $i++) if (isCubeFree($i)) echo $i . " ";}// Driver code$n = 20;printCubeFree($n);// This code is contributed by mits?> |
Javascript
<script>// JavaScript program to print all cube free// numbers smaller than or equal to n.// Returns true if n is a cube free// number, else returns false.function isCubeFree(n){ if (n == 1) return false; // Check for all possible divisible cubes for(let i = 2; i * i * i <= n; i++) if (n % (i * i * i) == 0) return false; return true;}// Print all cube free numbers smaller// than n.function prletCubeFree(n){ for(let i = 2; i <= n; i++) { if (isCubeFree(i)) { document.write ( i + " "); } }}// Driver codelet N = 20;prletCubeFree(N);// This code is contributed by code_hunt</script> |
Output:
2 3 4 5 6 7 9 10 11 12 13 14 15 17 18 19 20
An efficient solution is to use Sieve of Eratosthenes like technique, to wash out the non cube free numbers. Here we will create boolean sieve array and initialize it with true values. Now we will start iterating a variable ‘div’ from 2, and start marking multiples of cube of div as false as those will be the non cube free numbers. Then after this the elements left with value true will be the cube free numbers.
C++
// Efficient C++ Program to print all// cube free numbers smaller than or // equal to n.#include <bits/stdc++.h>using namespace std;void printCubeFree(int n){ // Initialize all numbers as not cube free bool cubFree[n + 1]; for (int i = 0; i <= n; i++) cubFree[i] = true; // Traverse through all possible cube roots for (int i = 2; i * i * i <= n; i++) { // If i itself is cube free if (cubFree[i]) { // Mark all multiples of i as not cube free for (int multiple = 1; i * i * i * multiple <= n; multiple++) { cubFree[i * i * i * multiple] = false; } } } // Print all cube free numbers for (int i = 2; i <= n; i++) { if (cubFree[i] == true) cout<<i<<" "; }}// Driver codeint main(){ printCubeFree(20); return 0;}// This code is contributed by Ajit. |
Java
// Efficient Java Program to print all cube free// numbers smaller than or equal to n.class GFG { public static void printCubeFree(int n) { // Initialize all numbers as not cube free boolean[] cubFree = new boolean[n + 1]; for (int i = 0; i <= n; i++) cubFree[i] = true; // Traverse through all possible cube roots for (int i = 2; i * i * i <= n; i++) { // If i itself is cube free if (cubFree[i]) { // Mark all multiples of i as not cube free for (int multiple = 1; i * i * i * multiple <= n; multiple++) { cubFree[i * i * i * multiple] = false; } } } // Print all cube free numbers for (int i = 2; i <= n; i++) { if (cubFree[i] == true) System.out.print(i + " "); } } public static void main(String[] args) { printCubeFree(20); }} |
Python3
# Efficient Python3 Program to # print all cube free# numbers smaller than or # equal to n.def printCubeFree(n): # Initialize all numbers # as not cube free cubFree = [1]*(n + 1); # Traverse through all # possible cube roots i = 2; while(i * i * i <= n): # If i itself # is cube free if(cubFree[i]==1): # Mark all multiples of # i as not cube free multiple = 1; while(i * i * i * multiple <= n): cubFree[i * i * i * multiple] = 0; multiple+=1; i+=1; # Print all cube # free numbers for i in range(2,n+1): if (cubFree[i] == 1): print(i,end=" ");# Driver Codeif __name__ == "__main__": printCubeFree(20);# This code is contributed # by mits |
C#
// Efficient C# Program to // print all cube free// numbers smaller than or // equal to n.using System;class GFG {public static void printCubeFree(int n){ // Initialize all numbers // as not cube free bool[] cubFree = new bool[n + 1];for (int i = 0; i <= n; i++) cubFree[i] = true;// Traverse through all // possible cube rootsfor (int i = 2; i * i * i <= n; i++) { // If i itself // is cube free if (cubFree[i]) { // Mark all multiples of // i as not cube free for (int multiple = 1; i * i * i * multiple <= n; multiple++) { cubFree[i * i * i * multiple] = false; } }}// Print all cube // free numbersfor (int i = 2; i <= n; i++) { if (cubFree[i] == true) Console.Write(i + " ");}}// Driver Codepublic static void Main(){ printCubeFree(20);}}// This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php// Efficient PHP Program to // print all cube free// numbers smaller than or // equal to n.function printCubeFree($n){ // Initialize all numbers // as not cube free $cubFree = array_fill(0,($n + 1), 1); // Traverse through all // possible cube roots $i = 2; while($i * $i * $i <= $n) { // If i itself // is cube free if($cubFree[$i] == 1) { // Mark all multiples of // i as not cube free $multiple = 1; while($i * $i * $i * $multiple <= $n) { $cubFree[$i * $i * $i * $multiple] = 0; $multiple += 1; } } $i += 1; } // Print all cube // free numbers for($i = 2; $i < $n + 1; $i++) if ($cubFree[$i] == 1) echo $i . " ";}// Driver CodeprintCubeFree(20);// This code is contributed // by mits?> |
Javascript
<script>// Efficient Javascript program to print// all cube free numbers smaller than or// equal to n. function printCubeFree(n){ // Initialize all numbers as not // cube free var cubFree = Array(n + 1).fill(false); for(i = 0; i <= n; i++) cubFree[i] = true; // Traverse through all possible cube roots for(i = 2; i * i * i <= n; i++) { // If i itself is cube free if (cubFree[i]) { // Mark all multiples of i as not cube free for(multiple = 1; i * i * i * multiple <= n; multiple++) { cubFree[i * i * i * multiple] = false; } } } // Print all cube free numbers for(i = 2; i <= n; i++) { if (cubFree[i] == true) document.write(i + " "); }}// Driver codeprintCubeFree(20);// This code is contributed by aashish1995 </script> |
Output:
2 3 4 5 6 7 9 10 11 12 13 14 15 17 18 19 20
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
