线筛sqrt(n)以内的素数,然后再求最小的可以整除素数,另外一个就是最大的素数
#include <iostream>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
int prime[n+1] = {0},p[n+1],top = 0;
prime[0] = prime[1] = 1;
for(int i=2;i <= n;i++)
{
if(!prime[i])
{
p[top++] = i;
}
for(int j=0;p[j] * i <= n && j < top;j++)
{
prime[p[j]*i] = 1;
if(p[j] % i == 0)
break;
}
}
for(int i=top-1;i >= 0;i--)
if(n % p[i] == 0)
{
cout<<p[i];
return 0;
}
}