无立方因子的数是指那些没有立方数作为因子的数。
立方数因子是指一个整数，它是一个立方数并且能够整除该数而没有余数。
例如，8是16的立方数因子，因为8是2的立方数（2*2*2 = 8），并且8除以16的余数为零。
因此，8和16都不是无立方数。
问题陈述
找出所有小于给定数字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
的中文翻译为：
解释
注意，列表中没有1、8和16。因为1和8本身就是立方数，而16是8的倍数。
有两种方法来解决这个问题。
方法一：暴力法
暴力破解的方法如下：
遍历所有数字直到n。
对于每个数字，遍历其所有的除数。
如果一个数的任何一个因数是一个立方数，那么这个数就不是无立方数。
否则，如果这些数的除数中没有一个是立方数，那么它就是一个无立方数。
打印数字。
Example
的翻译为：
示例
The program for this approach is as follows −
下面是一个C++程序，用于打印小于给定数字n的所有无立方数。
#includeusing 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
方法二：埃拉托斯特尼筛法技术
解决这个问题的高效方法将是埃拉托斯特尼筛法的概念。
它用于找出小于给定限制的素数。在这里，我们将筛选出不是立方数的数字来得到我们的解决方案。
方法如下−
创建一个大小为n的布尔列表。
将所有数字标记为true。这意味着我们目前已将所有数字标记为无立方数。
遍历所有小于n的可能的立方体。
遍历所有小于n的立方数的倍数。
将列表中所有这些倍数标记为假。这些数字不是立方数自由的。
遍历列表。打印列表中仍为真的数字。
输出将包括所有小于n的无立方数。
Example
的翻译为：
示例
The program for this approach is as follows −
下面是一个使用埃拉托斯特尼筛法打印小于给定数n的所有无立方数的C++程序。
#include#includeusing namespace std;//Find which numbers are cube free and mark others as false in the vector.void find_cube_free(vector&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 vectorv(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++程序提供了这两种方法的实现。
以上就是小于n的立方数自由数的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1445570.html
微信扫一扫 
支付宝扫一扫 
