篩選法又稱篩法，具體做法是：先把N個自然數按次序排列起來。1不是質數，也不是合數，要划去。第二個數2是質數留下來，而把2後面所有能被2整除的數都划去。2後面第一個沒划去的數是3，把3留下，再把3後面所有能被3整除的數都划去。3後面第一個沒划去的數是5，把5留下，再把5後面所有能被5整除的數都划去。這樣一直做下去，就會把不超過N的全部合數都篩掉，留下的就是不超過N的全部質數。因為希臘人是把數寫在塗臘的板上，每要划去一個數，就在上面記以小點，尋求質數的工作完畢後，這許多小點就像一個篩子，所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼篩”，簡稱“篩法”。（另一種解釋是當時的數寫在紙草上，每要划去一個數，就把這個數挖去，尋求質數的工作完畢後，這許多小洞就像一個篩子。）
基本介紹
- 中文名：篩選法
- 又稱：篩法
- 類型：算法
- 服務：程式設計
程式步驟,求自然數素數,實現一,實現二,實現三,實現四,
程式步驟
先解釋一下篩選法的步驟：
<1> 先將1挖掉(因為1不是素數)。
<2> 用2去除它後面的各個數，把能被2整除的數挖掉，即把2的倍數挖掉。
<3> 用3去除它後面的各數，把3的倍數挖掉。
<4> 分別用5…各數作為除數去除這些數以後的各數。
上述操作需要一個很大的容器去裝載所有數的集合，只要滿足上述條件，即2的倍數大於1的全部置0，3的倍數大於1的全部置0，4的倍數大於1的全部置0……一直到這個數據集合的末尾，這樣一來不為0的數就是素數了，然後按下標在裡面進行查找就好了
求自然數素數
實現一
1.抽象步驟
<1>先將1去掉
<2>將2的倍數去掉。
<3>將3的倍數去掉。
……
<i>將i的倍數去掉。
……
一直到A。
2.具體化
以數組array[n]為例，其中array[n]=n+1;
循環開始
<1> 判斷array[0]的值。
array[0]的值是1；不執行操作
<2> 判斷array[1]的值。
array[1]的值是2；
用array[1]去除它後面的array[2]、array[3]、array[4]……array[n]；
能被array[1]整除的，例如array[3](值為4）、array[5](值為6），全部置1；
即：if (array[i]%array[1]==0) array[i]=1;
i=2,3,4……n
<3> 判斷判斷array[2]的值。
array[2]的值是3；
用array[2]去除它後面的各數，把array[2]的倍數全部置1。
比如array[8]（值為9），array[14]（值為15），全部置為"1"。
即：if (array[i]%array[2]==0) array[i]=1;
i=3,4,5……n
<4> 判斷array[3]的值。
array[3]原本的值為4，但是經過步驟<2>，現array[3]的值為1；
換句話說，如果array[3]的值為1，那么它一定可以被 array[2] 和 array[3] 中的某一個整除。
所以array[3]曾經是合數，不執行操作。
………………………
<i> 判斷array[i]的值。
如果 array[i]==1，那么array[i]一定可以被array[2]、array[3]、……array[i-1]中的某一個數整除
所以曾經的array[i]是合數，不執行任何操作。
否則 array[i]!=1，那么array[i]是素數。
用array[i]去除array[i+1]、array[i+2]、……array[n]。
能被array[i]整除的各項，全部置1。
………………………
<n> 判斷array[n]的值。
如果 array[n]==1，那么array[n]一定可以被array[2]~array[n-1]中的一項整除。
所以array[n]是合數，不執行任何操作。
如果 array[n]！=1，那么array[2]~array[n-1]都不能將它整除。
所以 array[n]是素數。
循環結束。
經過以上循環，所有合數都被置“1”，輸出所有非“1”的array[]。
即if（array[i]！=1） printf("%d",array[i]);
程式結束。
3.代碼實現
#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; }