-
篩選法
鎖定
- 中文名
- 篩選法
- 所屬學科
- 數學
- 別 名
- 篩法
篩選法簡介
埃拉託斯特尼篩法，簡稱埃氏篩或愛氏篩，是一種由希臘數學家埃拉託斯特尼所提出的一種簡單檢定素數的算法。因為希臘人是把數寫在塗蠟的板上，每要劃去一個數，就在上面記以小點，尋求質數的工作完畢後，這許多小點就像一個篩子，所以就把埃拉託斯特尼的方法叫做“埃拉託斯特尼篩”，簡稱“篩法”。（另一種解釋是當時的數寫在紙草上，每要劃去一個數，就把這個數挖去，尋求質數的工作完畢後，這許多小洞就像一個篩子。）
要得到自然數n以內的全部素數，必須把不大於根號n的所有素數的倍數剔除，剩下的就是素數。先用2去篩，即把2留下，把2的倍數剔除掉；再用下一個質數，也就是3篩，把3留下，把3的倍數剔除掉；接下去用下一個質數5篩，把5留下，把5的倍數剔除掉；不斷重複下去......。
篩選法代碼
篩選法實現一
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");
}
----------------------純粹按“篩選法”原理實現--------------------------
篩選法實現三
此篩選法遵循了C程序模塊化的習慣，將篩選法獨立為一個函數在主函數裏調用，此代碼在VC6.0中完全可以直接使用。
#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;
}
篩選法實現五
primes([Cur|Upto]) -> % 提取列表首尾元素 case Cur =< math:sqrt(lists:last(Upto)) of true -> % 如果列表第一個元素小於等於輸入長度 [Cur] % 記錄列表首個元素 ++ primes ( [X || X <- Upto, % 針對除去首元素的列表， X rem Cur /= 0] % 篩去不能整除首元素的元素 ); % 遞歸調用自身 _ -> % 否則， [Cur|Upto] % 返回整個列表 end. main([]) -> io:write(primes(lists:seq(2,10000))). % 輸出 2 到 10000 的所有質數
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：38次歷史版本
- 最近更新： 叶月默笙