挑選法的C++完成

挑選法的C++完成。本站提示廣大學習愛好者：（挑選法的C++完成）文章只能為提供參考，不一定能成為您想要的結果。以下是挑選法的C++完成正文

挑選法

引見：
挑選法又稱篩法，是求不跨越天然數N（N>1）的一切質數的一種辦法。聽說是古希臘的埃拉托斯特尼（Eratosthenes，約公元前274～194年）創造的，又稱埃拉托斯特尼篩子。

詳細做法是：先把N個天然數順次序分列起來。1不是質數，也不是合數，要劃去。第二個數2是質數留上去，而把2前面一切能被2整除的數都劃去。2前面第一個沒劃去的數是3，把3留下，再把3前面一切能被3整除的數都劃去。3前面第一個沒劃去的數是5，把5留下，再把5前面一切能被5整除的數都劃去。如許一向做下去，就會把不跨越N的全體合數都篩失落，留下的就是不跨越N的全體質數。由於希臘人是把數寫在塗臘的板上，每要劃去一個數，就在下面記以小點，追求質數的任務終了後，這很多小點就像一個篩子，所以就把埃拉托斯特尼的辦法叫做“埃拉托斯特尼篩”，簡稱“篩法”。（另外一種說明是其時的數寫在紙草上，每要劃去一個數，就把這個數挖去，追求質數的任務終了後，這很多小洞就像一個篩子。）

用C++完成挑選法：
以經由過程挑選法求100之內的素數為例

#include<iostream>
using namespace std;
int main()
{
 int i,j,a[101];//這裡界說101年夜小的數組，是為了和天然數絕對應，即：a[2]對應天然數2
 for(i=2;i<100;i++)
     a[i]=1;//完成對數組的初始化操作
 for(i=2;i<100;i++){
  for(j=2*i;j<100;j+=i){
   a[j]=0;//對響應的倍數停止消除
  }
 }
 //履行輸入操作
 for(i=2;i<100;i++){
  if(a[i])
  cout<<i<<'\t';
 }
 cout<<endl;
 return 0;
}

一些思慮和優化
之前進修盤算素數的算法的時刻，有一個比擬廣泛的優化的算法。

也就是用

for(i=1;i<(j/2);i++)

或許

for(i=1;i<sqrt(j);i++)//應用sqrt()函數須要引入math.h這個頭文件

來替換

for(i=1;i<j;i++)

可以明顯的下降算法的龐雜度

一開端直接應用，不曉得是甚麼道理。後來看了看，本來道理是如許的：

以sqrt(j)取代i為例

求素數最根本的辦法，是用i去除以2到j-1之間的一切的整數，假如有可以整除的情形，則不是素數；假如都弗成以整除，則是素數。

而i=sqrt(j)*sqrt(j)

我們用i去除以2到sqrt(j)之間的一切的整數，這便可以籠罩2到i-1之間的一切的整數。

設2<k<sqrt(j)，則若j%k==0，則sqrt(j)<m=(j%k)<j-1。

也就是說，由於是除法運算求整除的運算，所以除以小的可以整除，可就是除以響應的年夜的可以整除。

優化以後的代碼：

#include<iostream>
#include<math.h>
using namespace std;
int main()
{
 int i,j,a[101];//這裡界說101年夜小的數組，是為了和天然數絕對應，即：a[2]對應天然數2
 for(i=2;i<100;i++)
     a[i]=1;//完成對數組的初始化操作
 for(i=2;i<sqrt(100);i++){
  for(j=2*i;j<100;j+=i){
   a[j]=0;//對響應的倍數停止消除
  }
 }
 //履行輸入操作
 for(i=2;i<100;i++){
  if(a[i])
  cout<<i<<'\t';
 }
 cout<<endl;
 return 0;
}