hdu2136Largest prime factor （關建在求素數，有點意思的題）

Problem Description Everybody knows any number can be combined by the prime number.
Now, your task is telling me what position of the largest prime factor.
The position of prime 2 is 1, prime 3 is 2, and prime 5 is 3, etc.
Specially, LPF(1) = 0.

Input Each line will contain one integer n(0 < n < 1000000).

Output Output the LPF(n).

Sample Input

1
2
3
4
5

0
1
2
1
3題意：求一個數的最簡因式中最大素數因子在所有的素數中位置，位置從0開始。分析：所有的數都可以用素數的倍數來表示，原因：數分為兩類：素數和非素數。非素數那麼一定可以分解得到最簡因式，素數不能分解，其最簡因式是本身。綜上所述：一個數的最簡因式中因子一定全是素數。方法一： 
#include
int prim[1000005]={0};
void init()
{
    int k;
    prim[1]=0; k=1;
    for(int i=2;i<1000000;i++)
    if(prim[i]==0)//i是素數
    {
      for(int j=i; j<1000000; j+=i)
        prim[j]=k;
        k++;
    }
}
int main()
{
    int n;
    init();
    while(scanf("%d",&n)>0)
        printf("%d\n",prim[n]);
}


方法二：
#include
int vist[1000005]={0},prim[1000005];
void init()
{
    int k;
    prim[1]=1; prim[2]=2;k=3;
    for(int i=3;i<1000000;i+=2)
    if(vist[i]==0)
    {
        prim[i]=k; k++;
        for(int j=i; j<1000000; j+=i)
        if(vist[j]==0)
        vist[j]=1;
    }
}
int main()
{
    int n,posit;
    init();
    while(scanf("%d",&n)>0)
    {
        posit=1;
        for(int i=2; ; i++)
            if(prim[n]==0)
            {
                if(prim[i]&&n%i==0)posit=i;
                while(n%i==0)n/=i;
            }
            else
            {
               if(n>posit)posit=n; break;
            }
            printf("%d\n",prim[posit]-1);
    }
}