素数判定方法
方法一：试除法
从2到sqrt(n)，依次试除
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool isPrime(ll n){
if(n<2)return 0;
for(int i=2;i*i<=n;i++)if(n%i==0)return 0;
return 1;
}
int main(){
ll n;cin>>n;
if(isPrime(n))cout<<n<<" is a Prime.";
else cout<<n<<" isn't a Prime.";
return 0;
}
方法二：费马素性测试
运用费马小定理判定素数，但不完全正确
方法三：Miller_Rabin素性测试
费马素性测试的改进版，是已知的最快的随机素数测试算法
例题：hdu2138
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll quickPow(ll a,ll b,ll m){
ll ans=1;
while(b){
if(b&1)ans=(ans*a)%m;
a=(a*a)%m;
b>>=1;
}
return ans;
}
bool witness(ll a,ll n){
ll u=n-1;int t=0;
while(!(u&1))u>>=1,t++;
ll x1,x2;
x1=quickPow(a,u,n);
for(int i=1;i<=t;i++){
x2=quickPow(x1,2,n);
if(x2==1&&x1!=1&&x1!=n-1)return 1;
x1=x2;
}
if(x1!=1)return 1;
return 0;
}
int Miller_Rabin(ll n,int s){
if(n<2)return 0;
if(n==2)return 1;
if(n%2==0)return 0;
for(int i=0;i<s&&i<n;i++){
ll a=rand()%(n-1)+1;
if(witness(a,n))return 0;
}
return 1;
}
int main(){
int T,n;
while(cin>>T){
int ans=0;
for(int i=1;i<=T;i++){
cin>>n;
ans+=Miller_Rabin(n,50);
}
cout<<ans<<'\n';
}
return 0;
}
质因数分解
方法一：欧拉筛
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e8+39+7,M = 1e7+39+7;
int prime[M];int vis[N];
int Solve(int n){
int k=0;
memset(vis,0,sizeof(vis));
memset(prime,0,sizeof(prime));
for(int i=2;i<=n;i++){
if(!vis[i])vis[i]=i,prime[k++]=i;
for(int j=0;j<k;j++){
if(i*prime[j]>n)break;
vis[i*prime[j]]=prime[j];
if(i%prime[j]==0)break;
}
}
return k;
}
int main(){
int n;cin>>n;
Solve(n);
cout<<vis[n];
return 0;
}
方法二：试除法
与判断素数的试除法代码相似
素数筛法
方法一：埃氏筛
轮流筛掉素数的倍数即可
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+39+7;
int prime[N];bool vis[N];
int Solve(int n){
int k=0;
memset(vis,0,sizeof(vis));
for(int i=2;i<=n;i++){
if(!vis[i]){
prime[++k]=i;
for(int j=i*2;j<=n;j=i*(j/i+1))vis[j]=1;
}
}
return k;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m;cin>>n;
int k=Solve(100000);
for(int i=1;i<=n;i++){
cin>>m;
if(m==prime[lower_bound(prime+1,prime+k+1,m)-prime])cout<<m<<' ';
}
return 0;
}
方法二：欧拉筛
埃氏筛的改进版，每次只用整数x的最小质因数筛掉，从而将时间复杂度降到线性
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e8+39+7,M = 1e7+39+7;
int prime[M];bool vis[N];
int Solve(int n){
int k=0;
memset(vis,0,sizeof(vis));
memset(prime,0,sizeof(prime));
for(int i=2;i<=n;i++){
if(!vis[i])prime[k++]=i;
for(int j=0;j<k;j++){
if(i*prime[j]>n)break;
vis[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
return k;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m,w;cin>>n>>m;
int k=Solve(n);
for(int i=1;i<=m;i++){
cin>>w;
cout<<prime[w-1]<<'\n';
}
return 0;
}