素数系列—素数筛选法

思路：

<1> 先将1挖掉(因为1不是素数)。

<2> 用2去除它后面的各个数，把能被2整除的数挖掉，即把2的倍数挖掉。

<3> 用3去除它后面的各数，把3的倍数挖掉。

<4> 分别用5…各数作为除数去除这些数以后的各数。 ——-《百度百科》
这样是素数都被筛选掉了，留下都不是素数。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include<time.h>

int a[100000001];   //默认赋值为0

int main()
{
    __int64 i,j,p,n;
    while (scanf("%I64d",&n)!=EOF&&n)
        {
            int count = 0;
            p = (int)sqrt(n*1.0);   //因子加到根号n就可以了
            a[0] = 1;
            a[1] = 1;   //0和1不是素数,所以赋值1
            for (i=2; i<=p; i++) //2~p作为除数筛选素数
                {
                    if (a[i]==0)
                        {
                            for (j=i*i; j<=n; j=j+i) //把2~p的倍数都赋值1表示不是素数
                                {
                                    a[j] = 1;
                                }
                        }
                }
            for (i=0; i<=n; i++)
                {
                    if (a[i]==0)  //留下的都是素数
                        count++;
                }
            printf("%d",count);
            printf("\n");
        }
    return 0;
}

上面代码的结果是输出素数个数，如果想输出全部素数，就直接输出a数组的下标即可

lsablog

素数系列—素数筛选法

Comment 取消