201412022200-hd-Largest prime factor

Largest prime factor

Time 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 Input

1
2
3
4
5

Sample Output

0
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;
}