暴力搞肯定不行，因此我们从小到大枚举素数，用n去试除，每次除尽，如果已经超过20，肯定是no。如果当前枚举到的素数的（20-已经找到的质因子个数）次方>剩下的n，肯定也是no。再加一个关键的优化，如果剩下的次数是1了，就直接判定剩下的n是否是素数。这样可以保证次方>=2，将我们需要枚举的素数限制在200w以内，就可做了。线性筛在这题虽然不必要，但是可以当个板子存下来。
Input
Output
Example
| input | output |
|---|---|
2 |
No |
1048576 |
Yes |
10000000000 |
Yes |
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
#define MAXP 2000000
#define EPS 0.00000001
ll n;
bool isNotPrime[MAXP+10];
int num_prime,prime[MAXP+10];
void shai()
{
for(long i = 2 ; i < MAXP ; i ++)
{
if(! isNotPrime[i])
prime[num_prime ++]=i;
for(long j = 0 ; j < num_prime && i * prime[j] < MAXP ; j ++)
{
isNotPrime[i * prime[j]] = 1;
if( !(i % prime[j]))
break;
}
}
}
bool is_prime(ll x)
{
if(x==1ll)
return 0;
for(ll i=2;i*i<=x;++i)
if(x%i==0)
return 0;
return 1;
}
int m=20;
int main()
{
scanf("%I64d",&n);
shai();
for(int i=0;i<num_prime;++i)
{
if((double)m*log((double)prime[i])-log((double)n)>EPS)
{
puts("No");
return 0;
}
while(n%(ll)prime[i]==0)
{
n/=(ll)prime[i];
--m;
}
if(m==0 && n==1)
{
puts("Yes");
return 0;
}
if(m<0 || (m==0 && n>1))
{
puts("No");
return 0;
}
if(n>1 && m==1)
{
if(is_prime(n))
{
puts("Yes");
return 0;
}
else
{
puts("No");
return 0;
}
}
}
return 0;
}
【线性筛】【筛法求素数】【素数判定】URAL - 2102 - Michael and Cryptography
原文：http://www.cnblogs.com/autsky-jadek/p/6304319.html