Miller——Rabin 素数测试

证明过程

https://blog.csdn.net/djz_zxd/article/details/53456321

代码：

1.误差大，编写简单

int is_not_prime[100000001];
int prime[10000001];
int num_prime;;
void Prime(int n)
{for(int i=2; i<=n; ++i){if( !is_not_prime[i])prime[num_prime++]=i;//关键处1for(int j=0; j<num_prime&&prime[j]*i<=n; ++j){is_not_prime[prime[j]*i]=1;if(!(i%prime[j]))//关键处2break;}}
}
int modular_exp(int a,int n,int mod)
{int ret=1;a%=mod;while(n){if(n&1)ret=a*ret%mod,n--;a=a*a%mod;n>>=1;}return ret;;
}
bool miller_rabin1(int n)//误差很大
{if(n==0||n==1)return false;if(n==2)return true;for(int i=2;i<10;++i){int a=rand()%(n-2)+2;if(modular_exp(a,n,n)!=a)return false;}return true;
}

2.基本没有误差

ll gcd(ll a,ll b)//求最大公约数
{return b?gcd(b,a%b):a;
}
ll multi(ll a,ll b,ll mod)//快速加法求模
{ll ret=0;while(b){if(b&1)ret=(ret+a)%mod,b--;a=(a+a)%mod;b>>=1;}return ret;
}
ll power(ll a,ll b,ll mod)
{ll ret=1;a%=mod;while(b){if(b&1)ret=multi(ret,a,mod),b--;a=multi(a,a,mod);b>>=1;}return ret;
}
bool miller_rabin2(ll n)
{if(n==2)return true;if(n<2||!(n&1))return false;ll m=n-1;ll cnt=0;while(!(m&1)){++cnt;m>>=1;}for(int i=0; i<Times; ++i)//Times==10{ll a=rand()%(n-1)+1;ll x=power(a,m,n);ll y=0;for(int j=0; j<cnt; ++j){y=multi(x,x,n);if(y==1&&x!=1&&x!=n-1)return false;x=y;}if(y!=1)return false;}return true;
}

整体代码：

#include<bits/stdc++.h>
using namespace std;
int is_not_prime[100000001];
int prime[10000001];
int num_prime;;
void Prime(int n)
{for(int i=2; i<=n; ++i){if( !is_not_prime[i])prime[num_prime++]=i;//关键处1for(int j=0; j<num_prime&&prime[j]*i<=n; ++j){is_not_prime[prime[j]*i]=1;if(!(i%prime[j]))//关键处2break;}}
}
int modular_exp(int a,int n,int mod)
{int ret=1;a%=mod;while(n){if(n&1)ret=a*ret%mod,n--;a=a*a%mod;n>>=1;}return ret;;
}
bool miller_rabin1(int n)//误差很大
{if(n==0||n==1)return false;if(n==2)return true;for(int i=2;i<10;++i){int a=rand()%(n-2)+2;if(modular_exp(a,n,n)!=a)return false;}return true;ll gcd(ll a,ll b)//求最大公约数
{return b?gcd(b,a%b):a;
}
ll multi(ll a,ll b,ll mod)//快速加法求模
{ll ret=0;while(b){if(b&1)ret=(ret+a)%mod,b--;a=(a+a)%mod;b>>=1;}return ret;
}
ll power(ll a,ll b,ll mod)
{ll ret=1;a%=mod;while(b){if(b&1)ret=multi(ret,a,mod),b--;a=multi(a,a,mod);b>>=1;}return ret;
}
bool miller_rabin2(ll n)
{if(n==2)return true;if(n<2||!(n&1))return false;ll m=n-1;ll cnt=0;while(!(m&1)){++cnt;m>>=1;}for(int i=0; i<Times; ++i)//Times==10{ll a=rand()%(n-1)+1;ll x=power(a,m,n);ll y=0;for(int j=0; j<cnt; ++j){y=multi(x,x,n);if(y==1&&x!=1&&x!=n-1)return false;x=y;}if(y!=1)return false;}return true;
}
int main()
{srand(time(NULL));int n;while(cin>>n){for(i=2;i<sqrt(n); ++i)//验证素数if(n%i==0)break;if(i<=sqrt(n)||n==1)printf("NO\n");elseprintf("YES\n");for(int i=2;i<n;++i)//方法1求得素数{if(miller_rabin1(i))cout<<i<<" ";}cout<<endl;for(int i=2;i<n;++i)//方法2求的素数{if(miller_rabin2(i))cout<<i<<" ";}cout<<endl;Prime(n);cout<<num_prime<<endl;for(int i=0;i<num_prime;++i)//线性筛素数cout<<prime[i]<<" ";cout<<endl;}
}