無立方因子的數(shù)是指那些沒有立方數(shù)作為因子的數(shù)。
立方數(shù)因子是指一個(gè)整數(shù)，它是一個(gè)立方數(shù)并且能夠整除該數(shù)而沒有余數(shù)。
例如，8是16的立方數(shù)因子，因?yàn)?是2的立方數(shù)（2*2*2 = 8），并且8除以16的余數(shù)為零。
因此，8和16都不是無立方數(shù)。
問題陳述
找出所有小于給定數(shù)字n的無立方數(shù)。
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.
登錄后復(fù)制
Explanation
的中文翻譯為：
解釋
注意，列表中沒有1、8和16。因?yàn)?和8本身就是立方數(shù)，而16是8的倍數(shù)。
有兩種方法來解決這個(gè)問題。
方法一：暴力法
暴力破解的方法如下：
遍歷所有數(shù)字直到n。
對(duì)于每個(gè)數(shù)字，遍歷其所有的除數(shù)。
如果一個(gè)數(shù)的任何一個(gè)因數(shù)是一個(gè)立方數(shù)，那么這個(gè)數(shù)就不是無立方數(shù)。
否則，如果這些數(shù)的除數(shù)中沒有一個(gè)是立方數(shù)，那么它就是一個(gè)無立方數(shù)。
打印數(shù)字。
Example
的翻譯為：
示例
The program for this approach is as follows ?
下面是一個(gè)C++程序，用于打印小于給定數(shù)字n的所有無立方數(shù)。
#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<<" ";
}
}
}
登錄后復(fù)制
輸出
The cube free numbers smaller than 17 are: 2 3 4 5 6 7 9 10 11 12 13 14 15
登錄后復(fù)制
方法二：埃拉托斯特尼篩法技術(shù)
解決這個(gè)問題的高效方法將是埃拉托斯特尼篩法的概念。
它用于找出小于給定限制的素?cái)?shù)。在這里，我們將篩選出不是立方數(shù)的數(shù)字來得到我們的解決方案。
方法如下?
創(chuàng)建一個(gè)大小為n的布爾列表。
將所有數(shù)字標(biāo)記為true。這意味著我們目前已將所有數(shù)字標(biāo)記為無立方數(shù)。
遍歷所有小于n的可能的立方體。
遍歷所有小于n的立方數(shù)的倍數(shù)。
將列表中所有這些倍數(shù)標(biāo)記為假。這些數(shù)字不是立方數(shù)自由的。
遍歷列表。打印列表中仍為真的數(shù)字。
輸出將包括所有小于n的無立方數(shù)。
Example
的翻譯為：
示例
The program for this approach is as follows ?
下面是一個(gè)使用埃拉托斯特尼篩法打印小于給定數(shù)n的所有無立方數(shù)的C++程序。
#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<<" ";
}
}
}
登錄后復(fù)制
輸出
The cube free numbers smaller than are: 2 3 4 5 6 7 9 10 11 12 13 14
登錄后復(fù)制
本文解決了找到小于n的無立方數(shù)的問題。我們看到了兩種方法：一種是蠻力法，另一種是使用埃拉托斯特尼篩法的高效方法。
C++程序提供了這兩種方法的實(shí)現(xiàn)。
以上就是小于n的立方數(shù)自由數(shù)的詳細(xì)內(nèi)容，更多請(qǐng)關(guān)注www.xfxf.net其它相關(guān)文章！
