HDU 2136 Largest prime factor(查找素数，筛选法)

题目梗概：求1000000以内任意数的最大质因数是第几个素数，其中定义 1为第0个，2为第1个，以此类推。

#include<string.h>

#include<stdio.h>

#include<math.h>

int a[],b[],c[];//b[i]表示i是第几个素数,c[k]表示k的最大素数是c[k],a[i]表示是不是素数

int main()

{

    int n,i,num,j;

    memset(a,,sizeof(a));

    a[]=;

       b[]=;

    num=;

    for(i=;i<;i++)//筛选法求素数

    {

        if(a[i]==)

        {

            for(j=i+i;j<;j=j+i)

            {

                a[j]=-;//不是素数置-1

                c[j]=i;

            }

            b[i]=num++;

            c[i]=i;

        }

    }

    while(scanf("%d",&n)!=EOF)

    {

        printf("%d\n",b[c[n]]);

    }

    return ;

}

扩展：

筛选法求（1~n内的）素数简介：

1：范围内所有数置0；

2：1置-1；

2：2的倍数置-1（除去2本身）；

3：3的倍数置-1（除去3本身）；

4：5的倍数置-1（除去5本身）；

5：7的倍数置-1（除去7本身）；

6：11的倍数置-1（除去11本身）；

7：下一个未置-1的整数置-1（除去自己本身）……直到n；

Ps：（1）：上述步骤都不要超出范围1~n；（2）：最后仍置0的为素数，置-1的为合数

完毕。

巴特西

HDU 2136 Largest prime factor(查找素数，筛选法)

最新文章

热门文章