標籤: 暫無標籤

篩選法又稱篩法,是求不超過自然數N(N>1)的所有質數的一種方法。據說是古希臘的埃拉托斯特尼(Eratosthenes,約公元前274~194年)發明的,又稱埃拉托斯特尼篩子。
具體做法是:先把N個自然數按次序排列起來。1不是質數,也不是合數,要劃去。第二個數2是質數留下來,而把2後面所有能被2整除的數都劃去。2後面第一個沒劃去的數是3,把3留下,再把3後面所有能被3整除的數都劃去。3後面第一個沒劃去的數是5,把5留下,再把5後面所有能被5整除的數都劃去。這樣一直做下去,就會把不超過N的全部合數都篩掉,留下的就是不超過N的全部質數。因為希臘人是把數寫在塗臘的板上,每要劃去一個數,就在上面記以小點,尋求質數的工作完畢后,這許多小點就像一個篩子,所以就把埃拉托斯特尼的方法叫做「埃拉托斯特尼篩」,簡稱「篩法」。(另一種解釋是當時的數寫在紙草上,每要劃去一個數,就把這個數挖去,尋求質數的工作完畢后,這許多小洞就像一個篩子。)

1C語言實現篩選法

先解釋一下篩選法的步驟:
<1> 先將1挖掉(因為1不是素數)。
<2> 用2去除它後面的各個數,把能被2整除的數挖掉,即把2的倍數挖掉。
<3> 用3去除它後面的各數,把3的倍數挖掉。
<4> 分別用5…各數作為除數去除這些數以後的各數。
上述操作需要一個很大的容器去裝載所有數的集合,只要滿足上述條件,即2的N次方的全部置0,3的N次方的全部置0,4的N次方的全部置0.。。。一直到這個數據集合的末尾,這樣一來不為0的數就是素數了,然後按下標在裡面進行查找就好了
篩選法程序如下
#include<stdio.h>
int main()
{
int x[100001];
int temp,n, i; //初始化數組
for(i=0;i<100001;i++)
x[i]=0; //初始化數組完成
"
x[0]=x[1]=1;//因為 0和1不能通過計算得到,所以只能手工置1 ,1即不是合數也不是質數
for(i=2;i<50000;i++)
{//循環數組中的每個數
if(x[i]==0){//如果該數所存的值為0,即第一次接觸此數
temp=2*i;//將它的二倍,及n倍(要小於100000) ,都置為1,因為這些數都能被i整除
while(temp<=100000)
{
x[temp]=1;
temp+=i;
}
}
}
scanf("%d",&n);
while(n != 0)
{
if(x[n]==0)
printf("素數\n");
else
printf("合數\n");
scanf("%d",&n);
}
return 0;
}

2篩選法求某項自然數A之內的素數(C語言)

實現二
「篩選法」原理:先把N個自然數按次序排列起來。1不是質數,也不是合數,要劃去。第二個數2是質數留下來,
而把2後面所有能被2整除的數都劃去。2後面第一個沒劃去的數是3,把3留下,再把3後面所有
能被3整除的數都劃去。3後面第一個沒劃去的數是5,把5留下,再把5後面所有能被5整除的數
都劃去...直至留下的數全為素數
----------------------純粹按「篩選法」原理實現--------------------------
#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");
}
----------------------純粹按「篩選法」原理實現--------------------------
上一篇[《幼幼近編》]    下一篇 [Double B 21]

相關評論

同義詞:暫無同義詞