NYOJ 520 & HDU 2136 Largest prime factor（筛法思想）

题目链接：Click here~~

题意是求出某个数n的最大素因子是第几个素数。

原以为是水题，没想到低估它了。

开始时我先把100W内的素数打表，然后用欧拉函数的做法，对每个数挨个分解质因子，得到最大的素因子，输出它的下标。

结果，悲剧的TLE了。

后来小冰告诉我，可以用筛法的思想做，我顿悟了。做法如下：

表中不在记录素数的值，而是直接记录素数的序数。

从2开始循环，当遇到为0的值时，证明它是素数，这时候把它的所有倍数（包括它本身）的值更新为这个素数的序数，也就同时标记为它们为非素数。

这样，每个数的序数可以保证是最大的。

#include <stdio.h>
const int M = 1000001;
int pos[M];
void ac_table()
{
    int top=0;
    for(int i=2;i<M;i++)
        if(pos[i] == 0)
        {
            ++top;
            for(int j=i;j<M;j+=i)
                pos[j] = top;
        }
}
int main()
{
    int n;
    ac_table();
    while(~scanf("%d",&n))
    {
        printf("%d\n",pos[n]);
    }
    return 0;
}

后来看到小牛的代码，才发现自己之前写的这类分解素因子的代码有个地方一直写繁了，养成了不好的习惯。

以前做的题都数据比较小，所以没有发现。这次数据大了，效率暴露无疑。

实践证明，做些题目还是有好处的，可以发现自己以前没有发现的错误。

#include <stdio.h>
const int M = 1000001;
int prime[78500];
int pos[M];
void ac_table()
{
    int top=0;
    for(int i=2;i<M;i++)
        if(pos[i] == 0)
        {
            prime[++top]=i;                     //放入素数表
            pos[i] = top;                       //记录此素数的序数
            for(int j=2*i;j<M;j+=i)
                pos[j] = -1;                    //标记为非素数
        }
}
int main()
{
    int n;
    ac_table();
    while(~scanf("%d",&n))
    {
        int ans=0;
        for(int i=1;prime[i]*prime[i]<=n;i++)   //循环结束条件是亮点，以前我写的是n!=1
            while(n%prime[i]==0)
            {
                ans = i;                        //ans记录序数
                n /= prime[i];
            }
        if(n!=1)                                //还没分解完，说明此时n是素数
            ans = pos[n];                       //直接把n的序数赋给ans
        printf("%d\n",ans);
    }
    return 0;
}