首頁 > 後端開發 > C++ > 主體

小於n的立方數自由數

WBOY
發布: 2023-09-21 17:25:02
轉載
812 人瀏覽過

小於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的所有無立方數。

#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
登入後複製

方法二:埃拉托斯特尼篩法技術

解決這個問題的高效方法將是埃拉托斯特尼篩法的概念。

它用來找出小於給定限制的質數。在這裡,我們將篩選出不是立方數的數字來得到我們的解。

方法如下−

  • 建立一個大小為n的布林清單。

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

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

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

  • 將清單中所有這些倍數標記為假。這些數字不是立方數自由的。

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

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

#Example

的翻譯為:

範例

The program for this approach is as follows −

下面是一個使用埃拉托斯特尼篩法列印小於給定數n的所有無立方數的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<<" ";
      }
   }
}
登入後複製

輸出

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

本文解決了找到小於n的無立方數的問題。我們看到了兩種方法:一種是蠻力法,另一種是使用埃拉托斯特尼篩法的高效方法。

C 程式提供了這兩種方法的實作。

以上是小於n的立方數自由數的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:tutorialspoint.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
最新問題
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網:公益線上PHP培訓,幫助PHP學習者快速成長!