篩選法

篩選法又稱篩法,具體做法是:先把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");}----------------------純粹按“篩選法”原理實現--------------------------

實現三

此篩選法遵循了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; }

相關詞條

熱門詞條

聯絡我們