素数判断的方法

Green

　　1.根据定义 时间复杂度O(n)

template<typename T>
bool is_prime(T n)
{
  for(int i=2; i < n; i++)
    if(n % i == 0)
      return false;
  return true;
}

　　2.优化 时间复杂度O(n^(1/2))

template<typedef T>
bool is_prime(T n)
{
  for(int i=2; i*i<=n; i++)
    if(n % i == 0)
      return false;
  return true;
}

　　3.埃氏筛法 （打表，求某区间内的素数个数）

const int N=1e5+5;
int prime[N],sum[N];
bool is_pr[N];
int cnt;
void sieve()
{
  cnt=0;
  mem(is_pr,0);
  for(int i=2; i*i<=N; i++)
    if(!is_pr[i])
      for(int j=i*i; j<=N; j+=i)
        is_pr[j]=1;
  for(int i=2; i<N; i++) if(!is_pr[i]) prime[cnt++]=i;
}

　　求区间[a,b]内的素数个数就转换为[2,b]-[2,a]
　　4.Miller-Rabbin随机性素数测试方法 时间复杂度O(s(logn)^3)
可用于 判断大数（2^63）是否为素数
可参考算导P565 或 https://wenku.baidu.com/view/83b3f2105f0e7cd1842536ac.html

const int s=50; ///Miller-Rabbin算法的复杂度与s有关 2^(-s)为出错率
template<typename T>
T pow_mod(T a,T b,T mod)
{
  T ans=1;
  while(b)
  {
    if (b&1) ans=ans*a%mod;
    a = a*a%mod;
    b >>= 1;
  }
  return ans;
}
bool MRT(ll n)
{
  if(n == 2) return true;///2的时候 特判
  for(ll i=1; i <= s; i++)
  {
    ll tmp = rand()%(n-1)+1;
    if(pow_mod(tmp,n-1,n) != 1)
      return false;///非素数
  }
  return true;///素数
}