记录编号	324944	评测结果	AAAAAAAAAA
题目名称	[NOIP 2012PJ]质因数分解	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.170 s
提交时间	2016-10-18 21:22:11	内存使用	9.85 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
 
using namespace std;
 
int n;
vector<int> a;
bool have[10000001];
 
 
int f(int x)
{
	int k=1;
	int i=0,t=x;
	while(a[i]<=t)
	{
		if(x%a[i]==0)
		{
		 k=max(a[i],x/a[i]);
		 break;
	    }
	    i++;
	}
	return k;
}
 
int main ()
{
    freopen("prime.in","r",stdin);
    freopen("prime.out","w",stdout);	
    int n=1000000;
	memset(have, 1, sizeof(have));
	for ( int i = 2 ; i <= n ; ++i )
	{
		if ( have[ i ] )
			a.push_back(i);
		for (int j = 0; j < a.size(); ++j)
		{
			int t = a[j];
			if ( i * t > n)
				break;
			have[ i * t ] = 0;
			if ( i % t == 0 )
				break;
		}
	}
	int ans=0,maxx=0,t1;
    cin>>n;
    t1=f(n);
	cout<<t1;
}