Largest prime factor Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6130 Accepted Submission(s): 1886
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
Sample Output
0 1 2 1 3
Author
Wiskey
Source
HDU 2007-11 Programming Contest_WarmUp
Recommend
威士忌
题意: 题意比较难读,每一个质数都有他的顺序号,例如1为第0个,2为1,3为2,5为3,………给你一个数让你算出这个数 最大质因数的顺序号。
思路: 发现了一个问题,一个很大的数组被定义在main函数中时编译器运行不了,但被定义在main函数之外时就能运行。本题 打表。从2开始枚举每一个数,若为质数那么只要是小于等于此质数的数与他相乘得到的数的最大质因数就是此质数, 如果不是质数,那么只要小于等于此数的数和他相乘得到的数的最大质因数就是两个数的最大质因数中大的那个。
代码:
#include<iostream>
#include<string>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;
int max(int x,int y)
{
return x>y?x:y;
}
int a[1000000];
int main()
{
int n;
memset(a,-1,sizeof(a));
a[1]=0;
int k=1;
for(int i=2;i<=1000000;i++)
{
if(a[i]==-1)
{ a[i]=k++;
for(int j=2;j<=i&&i*j<=1000000;j++)
{
a[i*j]=a[i];
}
}
else
{
for(int j=2;j<=i&&i*j<=1000000;j++)
{
if(a[i*j]==-1)
a[i*j]=max(a[i],a[j]);
}
}
}
while(scanf(“%d”,&n)!=EOF)
{
printf(“%d\n”,a[n]);
}
return 0;
}