Largest prime factorTime Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7195 Accepted Submission(s): 2554
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 Input1
2
3
4
5
Sample Output0
1
2
1
3题目大意 给定1--1000000中任意一个数，输出其最大质因子数是第几个质数。解题思路 为了不超时肯定需要打表，我原来的思路是一步一步求，第一步打表1--1000000中的素数，第二步打表1--1000000中的素数是第几个，第三部打表1--1000000中的所有数的最大质因子，然后两个数组相结合输出结果。可惜这种方法太麻烦，果断超时。 思索了好久，还是采用了打表的方法，跟素数打表差不多，但是不只是因为素数而将其标记，而是如果是素数，则将其及其倍数全部用这个素数的位置来标记。因为i不断变化，所以如果是6，第一次标记为2，后面可以用3来标记替换。代码#include
#include
int a[1100000];
int main()
{
int n,i,j,now;
memset(a,0,sizeof(a));//初始化，将其全部标记为0
a[1]=0;
now=0;//标记位置，也就是第几个
for(i=2;i<=1000000;i++)
{
if(a[i]==0)//如果其是质数
{
now++;
for(j=i;j<=1000000;j+=i)
a[j]=now;//则将其在范围内的所有倍数都用now标记，
}//i不断增大，则最大质因子不断被替换。
}
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",a[n]);
}
return 0;
}
|
