Largest prime factor

1
2
3
4
5

0
1
2
1
3
题目大意
   给定1--1000000中任意一个数，输出其最大质因子数是第几个质数。
解题思路
   为了不超时肯定需要打表，我原来的思路是一步一步求，第一步打表1--1000000中的素数，第二步打表1--1000000中的素数是第几个，第三部打表1--1000000中的所有数的最大质因子，然后两个数组相结合输出结果。可惜这种方法太麻烦，果断超时。
   思索了好久，还是采用了打表的方法，跟素数打表差不多，但是不只是因为素数而将其标记，而是如果是素数，则将其及其倍数全部用这个素数的位置来标记。因为i不断变化，所以如果是6，第一次标记为2，后面可以用3来标记替换。
代码
#include<stdio.h>
#include<string.h>
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;
}