素数系列—素数打表法 | LSABLOG

首页 » Program » C/C++ » 正文

素数系列—素数打表法

素数打表:把生成的素数存在一个表(数组)中,以达到方便存取和省时间的效果。

//要判断一个数是否素数,只需用2~sqrt(n)的数除即可(任何一个数的最大因子都小于等于此数的平方根)---[1]
//一个合数总能分解成几个素数的乘积---[2]

#include <stdio.h>
int main()
{
    int k = 2,count = 1,p[100005],w = 3,str[100005],i,j,n;
    p[1] = 2;   //p数组用来存素数表
    str[0] = 0,str[1] = 0,str[2] = 1;   //str数组用来存素数个数
    for (i=3; i<=100000; i=i+1)
        {
            count = 1;
            for (j=1; p[j]*p[j]<=i; j++) //[1][2]
                {
                    if (i % p[j]==0)
                        {
                            count = 0;
                            str[w] = str[w-1];   //如果不是素数,这个位置的素数个数和上一个位置一样
                            w++;
                            break;
                        }
                }
            if (count==1)
                {
                    p[k++] = i;   //打表
                    str[w] = str[w-1] + 1;   //如果是素数,就加1
                    w++;
                }
        }
    while (scanf("%d",&n)!=EOF&&n)
        {
            printf("%d\n",str[n]);   //直接输出就可以省很多时间
            k = 2;
            w = 3;
            count = 1;
        }
    return 0;
}

上面代码的i在循环里面其实可以i = i + 2,因为大于2的偶数肯定不是素数啦,不过这里我为了能够输出1~n范围的素数个数,而利用了str数组记录素数个数,为了让w变量和i变量同步,所以用了i = i + 1。
如果只是为了输出素数就可以i = i + 2,,再把代码做些改动即可。

赞 (0)

Comment