质数判断不同方法 题解 100% AC

1.暴力枚举法（试除法）：

#include <bits/stdc++.h>
using namespace std;
bool isprime(int x){
    if(x<2)return 0;
    for(int i=2;i*i<=x;i++)if(x%i==0)return 0;
    return 1;
}
int main(){
    int x;cin>>x;
    if(isprime(x))cout<<"Yes";
    else cout<<"No";
    return 0;
}

2.埃拉托斯特尼筛法（埃氏筛）（RE）：

#include <bits/stdc++.h>
using namespace std;
bool prime[2141568383];
bool isprime(int x){
    if(x<2)return 0;
    for(int i=2;i<=sqrt(x);i++){
        if(!prime[i]){
            for(int j=2*i;j<=x;j+=i){
                if(j==x)return 0;
                prime[j]=1;
            }
        }
    }
    return !prime[x];
}
int main(){
    int x;cin>>x;
    if(isprime(x))cout<<"Yes";
    else cout<<"No";
    return 0;
}

3.欧拉筛（线性筛）（RE）：

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e8+10;
bool isPrime[MAX];
int primes[MAX], cnt = 0;
bool checkPrime(int n) {
    if(n < 2) return false;
    for(int i = 2; i <= n; i++) isPrime[i] = true;
    for(int i = 2; i <= n; i++) {
        if(isPrime[i]) primes[cnt++] = i;
        for(int j = 0; j < cnt && i * primes[j] <= n; j++) {
            isPrime[i * primes[j]] = false;
            if(i % primes[j] == 0) break;
        }
    }
    return isPrime[n];
}
int main(){
    int x;cin>>x;
    if(checkPrime(x))cout<<"Yes";
    else cout<<"No";
    return 0;
}

4.超优化枚举法：

#include <bits/stdc++.h>
using namespace std;
bool isprime(int x){
    if(x<2)return 0;
    int i=2;
    while(x%i!=0&&i*i<=x) i++;
    return i*i>x;
}
int main(){
    int x;cin>>x;
    if(isprime(x))cout<<"Yes";
    else cout<<"No";
    return 0;
}

5.米勒-拉宾素性测试‌：

#include <bits/stdc++.h>
using namespace std;
int mod_pow(int a,int b,int m) {
	int res=1;
	a%=m;
	while(b>0) {
		if(b&1)res=res*a%m;
		a=a*a%m;
		b>>=1;
	}
	return res;
}
bool isprime(int n) {
	if(n<=1) return 0;
	if(n<=3) return 1;
	int d=n-1;
	while(d%2==0)d/=2;
	for(int a: {2,3,5,7,11,13,17,19,23,29,31,37}) {
		if(n==a) return 1;
		if(mod_pow(a,d,n)==1) continue;
		int r=d;
		while (r<n-1&& mod_pow(a,r,n)!=n-1)r*=2;
		if(r>=n-1)return 0;
	}
	return 1;
}
int main() {
	int x;
	cin>>x;
	if(isprime(x))cout<<"Yes";
	else cout<<"No";
	return 0;
}