篩選法又稱篩法,具體做法是:先把N個自然數按次序排列起來。1不是質數,也不是合數,要划去。第二個數2是質數留下來,而把2後面所有能被2整除的數都划去。2後面第一個沒划去的數是3,把3留下,再把3後面所有能被3整除的數都划去。3後面第一個沒划去的數是5,把5留下,再把5後面所有能被5整除的數都划去。這樣一直做下去,就會把不超過N的全部合數都篩掉,留下的就是不超過N的全部質數。因為希臘人是把數寫在塗臘的板上,每要划去一個數,就在上面記以小點,尋求質數的工作完畢後,這許多小點就像一個篩子,所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼篩”,簡稱“篩法”。(另一種解釋是當時的數寫在紙草上,每要划去一個數,就把這個數挖去,尋求質數的工作完畢後,這許多小洞就像一個篩子。)
基本介紹
- 中文名:篩選法
- 又稱:篩法
- 類型:算法
- 服務:程式設計
程式步驟
求自然數素數
實現一
#include<cstdio>int main(int argc, char const *argv[]){ //if it is prime ,it's 0 bool prime[1000]; for (int i = 0; i < 1000; ++i) { prime[i]=0; } prime[0]=1; prime[1]=1; for(int i=2;i<1000;i++){ if(prime[i]==0){ for(int j=i*2;j<1000;j+=i) prime[j]=1; } } for (int i = 0; i < 1000; ++i) { if(prime[i]==0)printf("%d ",i ); } return 0;}
實現二
#include<stdio.h>void main(){ int i; int N,count,p=0; int r[1001];//限制數據量大小為1000 printf("你想求多少以內的素數:"); scanf("%d",&N); for(i=1;i<=N;i++)//為方便計,從1起 r[i]=1; count=2;//篩選起點為2 while(count<=N/2) //顯然:count不會超過N/2,必能使留下的數全為素數。 { for(i=count+1;i<=N;i++) { if(r[i]==1&&i%count==0) r[i]=0; } for(i=count+1;i<=N;i++) { if(r[i]==1) { count=i; break; } } } printf("%d以內的素數為:\n",N); for(i=2;i<=N;i++) if(r[i]==1) { p++; printf("%d ",i); if(p%10==0)//增設p為輸出換行 printf("\n"); } printf("\n");}----------------------純粹按“篩選法”原理實現--------------------------
實現三
#include"stdio.h"#include"string.h"int a[10000]; //定義一個容器int n,i,j,k,count=0,temp,cs=1;int SXF(int n) //篩選法,n為範圍{ for(i=0;i<n;i++) //在定義的範圍內循環 { if(a[i]<=1) //判斷當前數組存放數值是否大於1 continue; //為真,結束本次循環 temp=2*a[i]; //為假,temp賦值為當前數值的兩倍 while(temp<n) //temp不能超過範圍 { a[temp]=1; //將通過的數值的倍數全部賦值為1 temp=temp+a[i]; } } return 0;}void main(){ for(j=0;j<10000;j++) //容器賦值 { a[j]=j; } printf("請輸入你要查找素數的範圍(1~10000):"); scanf("%d",&n); SXF(n); printf("範圍內的素數:\n"); for(k=0;k<n;k++) { if(a[k]<=1) //因為合數已經全部賦值為1,所以通過都是素數 continue; printf("%d ",a[k]); count++; while(count>=cs) //以下可不加,為楊輝三角格式排列 { printf("\n"); count=0; cs++; } } printf("\n");}
實現四
#include<stdio.h>int_tmain(intargc,_TCHAR*argv[]){ intnum=100; inta[100]; for(inti=0;i<num;i++) { a[i]=i+2; } for(inti=1;i<num-1;i++) //i+1作為除數 { for(intj=i+1;j<num;j++) //a[j]作為被除數 { if(a[j]!=0&&a[j]%(i+1)==0) { a[j]=0; //非素數置零 } } } for(inti=1,n=0;i<num;i++) { if(a[i]!=0) { printf("%d\t",a[i]); if(++n%10==0) //十個一組輸出 { printf("\n"); } } } printf("\n"); return0; }