小於 n 的無立方數

---

無立方數是指沒有立方數因子的數。

立方數因子是指一個整數，它是某個整數的立方，並且能夠整除該數。

例如，8 是 16 的一個立方數因子，因為 8 是 2 的立方 (2*2*2 = 8)，並且 8 可以整除 16，餘數為零。

因此，8 和 16 都不是無立方數。

問題陳述

找到所有小於給定數字 n 的無立方數。

示例

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.

解釋

注意列表中沒有 1、8 和 16。因為 1 和 8 本身就是立方數，而 16 是 8 的倍數。

解決這個問題有兩種方法。

方法 1：暴力法

暴力法如下：

• 遍歷所有小於 n 的數字。

• 對於每個數字，遍歷其所有因子。

• 如果數字的任何因子是立方數，則該數字不是無立方數。

• 否則，如果數字的任何因子都不是立方數，則它是一個無立方數。

• 列印該數字。

示例

此方法的程式如下：

下面是一個 C++ 程式，用於列印所有小於給定數字 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<<" ";
      }
   }
}

輸出

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

方法 2：埃拉托色尼篩法

解決此問題的有效方案是使用埃拉托色尼篩法的概念。

它用於查詢小於給定限制的所有素數。在這裡，我們將篩選出不是無立方數的數字以獲得我們的解決方案。

方法如下：

• 建立一個大小為 n 的布林列表。

• 將所有數字標記為真。這意味著我們目前已將所有數字標記為無立方數。

• 遍歷所有小於 n 的可能的立方數。

• 遍歷小於 n 的立方數的所有倍數。

• 在列表中將所有這些倍數標記為假。這些數字不是無立方數。

• 遍歷列表。列印列表中仍然為真的數字。

• 輸出將包含所有小於 n 的無立方數。

示例

此方法的程式如下：

下面是一個 C++ 程式，使用埃拉托色尼篩法列印所有小於給定數字 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<<" ";
      }
   }
}

輸出

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

本文解決了查詢小於 n 的無立方數的問題。我們看到了兩種方法：一種是暴力法，另一種是使用埃拉托色尼篩法的有效方法。

兩種方法都提供了 C++ 程式。