题目描述
每个人都知道任何数字都可以由素数组合。
现在,你的任务是告诉我给定一个常数求最大的素数因子的位置(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;
}
解析
暂无