3327: 求素数因子的位置

题目描述

每个人都知道任何数字都可以由素数组合。
现在，你的任务是告诉我给定一个常数求最大的素数因子的位置（largest prime factor.）。
例如素数2的位置为1，素数3位置为2，素数5的位置为3 ……
那么4的最大素因子为2，那么LPF(4)=1,同理LPF（8）=1,而LPF（6）=2，因为最大素因子是3 ；
LPF（9）=2,因为9=3*3，最大素因子为3……
特别地，LPF（1）= 0。

输入

每行将包含一个整数n（0 <n <1000000）。

输出

输出 LPF(n).

样例输入

1
2
3
4
5

样例输出

0
1
2
1
3

参考代码

#include<stdio.h>
int a[1000000];
int main() 
{
    int m,n,i,j;
    int s=0;
    while(~scanf("%d",&n)) 
    {
        s=0;
        if(n==1)
                    printf("0n");
        else
        {
            for(i=2;i<=n;i++)
             a[i]=1;
                    for(i=2;i<=n;i++)
                   if(a[i]==1)
                    {
                    for(j=2;j*i<=n;j++)
                     a[j*i]=0;
                  }
                  for(i=2;i<=n;i++)
                  {
                    if(a[i]==1)
                       {
                          a[s]=i;
                          s++;
                       }
                 }
        for(i=0;i<s;i++)
        {
            if(n%a[i]==0){
             m=i;
            }
        }
        printf("%dn",m+1);
    }
    }
    return 0;
}

解析

暂无