小于 n 的无立方数
data structurec++server side programming
无立方数是没有立方因子的数。
立方因子是指一个整数，它是立方数，除以该数的余数为零。
例如，8 是 16 的立方因子，因为 8 是 2 的立方数(2*2*2 = 8)，而 8 除以 16 的余数为零。
因此，8 和 16 都不是无立方数。
问题陈述
找出所有小于给定数字 n 的无立方数。
示例
让我们通过一个例子来理解这个问题。 假设 n = 15， 因此，我们必须找到所有小于 15 且不能分解立方体的数字。 解决方案将是:2、3、4、5、6、7、9、10、11、12、13、14。 再举一个例子， 假设 n = 20。 数字是 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;
// 如果数字无立方数，则此函数返回 true。
// 否则返回 false。
bool is_cube_free(int n){
if(n==1){
return false;
}
//遍历所有小于 n 的立方体
for(int i=2;i*i*i<=n ;i++){
//如果立方体可以完全整除 n，则返回 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;
//遍历所有小于n的数字
for(int i=1;i<n;i++){
//如果数字没有立方体，则打印它。
if(is_cube_free(i)){
cout<<i<<" ";
}
}
}
输出
小于 17 的立方自由数有: 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;
//查找哪些数字是无立方数，并在向量中将其他数字标记为假。
void find_cube_free(vector<bool>&v, int n){
//遍历所有立方数小于 n 的数字
for(int i=2;i*i*i<n;i++){
//如果 i 不是无立方体的，那么它的倍数也将被标记为 false
if(v[i]==true){
//将 i 的立方的所有倍数标记为非立方数。
for(int j=1;i*i*i*j<n;j++){
v[i*i*i*j] = false;
}
}
}
}
int main(){
int n = 15;
//用于存储哪些数字是可解立方数的向量
//最初，我们将所有数字设置为可解立方数
vector<bool>v(n,true);
find_cube_free(v,n);
cout<<"小于的立方自由数为:"<<endl;
//遍历向量并打印可解立方数
for(int i=2;i<n;i++){
if(v[i]==true){
cout<<i<<" ";
}
}
}
输出
小于的立方自由数为: 2 3 4 5 6 7 9 10 11 12 13 14
本文解决了查找小于 n 的立方自由数的问题。我们看到了两种方法:一种是强力方法，另一种是使用埃拉托斯特尼筛法的高效方法。
为这两种方法提供了 C++ 程序。
