小于n的立方数自由数

无立方因子的数是指那些没有立方数作为因子的数。

立方数因子是指一个整数，它是一个立方数并且能够整除该数而没有余数。

例如，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的所有无立方数。

WeWedding婚纱影楼小程序

婚纱影楼小程序提供了一个连接用户与影楼的平台，相当于影楼在微信的官网。它能帮助影楼展示拍摄实力，记录访客数据，宣传优惠活动。使用频率高，方便传播，是影楼在微信端宣传营销的得力助手。功能特点：样片页是影楼展示优秀摄影样片提供给用户欣赏并且吸引客户的。套系页是影楼根据市场需求推出的不同套餐，用户可以按照自己的喜好预定套系。个人中心可以查看用户预约的拍摄计划，也可以获取到影楼的联系方式。

下载

#include
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:"<
输出
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
#include
using 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*iv(n,true);
   find_cube_free(v,n);
   cout<<"The cube free numbers smaller than are:"<
输出
The cube free numbers smaller than are:
2 3 4 5 6 7 9 10 11 12 13 14

本文解决了找到小于n的无立方数的问题。我们看到了两种方法：一种是蛮力法，另一种是使用埃拉托斯特尼筛法的高效方法。
C++程序提供了这两种方法的实现。