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.
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
Recommend
威士忌
思路:题意是输入一个数,输出它的最大因子是第几位素数,可以采取打表的方法,对第一个素数以及第一个素数的倍数都输出1,第二个素数及其倍数都输出2,以此类推。
#include<stdio.h> #include<cstring> #include<algorithm> #include<math.h> #include<iostream> using namespace std; int a[1000000]; int main() { int i,j,k=0,n; memset(a,0,sizeof(a)); for(i=2;i<1000000;i++) { if(a[i]==0) { k++; for(j=i;j<1000000;j=j+i) a[j]=k; } } while(scanf("%d",&n)!=EOF) { printf("%d\n",a[n]); } return 0; }