HDU 2136 Largest prime factor

Sol：筛法求素数打表时预处理下即可。

#include <cstdio>  
#include <cstring>  
  
using namespace std;  
  
const int maxisp = 1000000 + 10;  
const int maxp = 1000000 + 10;  
  
int num,n;  
int prime[maxp];  
int isprime[maxisp];  
  
inline void get_prime()  
{  
    num=1;  
    for(int i=2;i<=maxisp;i++)  
        if(!isprime[i])  
        {  
            prime[i]=num++;  
            for(int j=1;j*i<=maxisp;j++)  
            {
            	isprime[i*j]=1;
				prime[i*j]=prime[i];  
            }
        }  
}

int main()
{
	prime[1]=0;
	get_prime();
	int N;
	while(~scanf("%d",&N))
		printf("%d\n",prime[N]);
	return 0;
}

HDU 2136 Largest prime factor

原文：http://blog.csdn.net/imutzcy/article/details/18951285