素数判断的方法
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,sum;
bool is_pr;
int cnt;
void sieve()
{
cnt=0;
mem(is_pr,0);
for(int i=2; i*i<=N; i++)
if(!is_pr)
for(int j=i*i; j<=N; j+=i)
is_pr=1;
for(int i=2; i<N; i++) if(!is_pr) prime=i;
} 求区间内的素数个数就转换为-
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;///素数
}
文档来源：51CTO技术博客https://blog.51cto.com/u_13696685/2990630
页:
[1]