朴素判断查找

。。。略

埃拉托斯特尼筛法(埃式筛,Sieve of Eratosthenes)

核心思想

从小到大标记合数，未被标记的就是质数

实现

竞赛常用范围n<=1e7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int N=1e7;
bool isPrime[N+1];
vector<int>primes;

void sieve(int n){
    fill(isPrime,isPrime+n+1,true);
    isPrime[0]=isPrime[1]=false;

    for(int i=2;i*i<=n;++i){
        if(isPrime[i]){
            for(int j=i*i;j<=n;j+=i){
                isPrime[j]=false;
            }
        }
    }

    for(int i=2;i<=n;++i){
        if(isPrime[i])
            primes.push_back(i);
    }
}

线性筛(欧拉筛，Linear Sieve)

优化版筛法，保证每个合数只被最小质因子标记一次,比埃式筛快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const int N=1e7;
int isPrime[N+1];
vector<int>primes;

void linearSieve(int n){
    for(int i=2;i<=n;++i){
        if(!isPrime[i])primes.push_back(i);
        for(int p:primes){
            if(p*i>n)break;
            isPrime[p*i]=1;
            if(i%p==0)break;
        }
    }
}

分段筛法(Segmented Sieve)

用于范围很大(如1e12)但只查某个区间[L,R]

  1. 先筛出sqrt(R)以内的质数
  2. 用这些质数去标记[L,R]内的合数
  3. 未被标记的就是质数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<long long> segmentedSieve(long long L, long long R) {
    long long lim = sqrt(R);
    vector<int> primes;
    vector<bool> mark(lim+1, true);
    for (int i = 2; i <= lim; i++) {
        if (mark[i]) {
            primes.push_back(i);
            for (int j = i*i; j <= lim; j += i) mark[j] = false;
        }
    }
    vector<bool> isPrime(R-L+1, true);
    for (int p : primes) {
        for (long long j = max(1LL * p * p, (L+p-1)/p * 1LL * p); j <= R; j += p)
            isPrime[j-L] = false;
    }
    vector<long long> res;
    for (long long i = 0; i <= R-L; i++)
        if (isPrime[i] && i+L > 1) res.push_back(i+L);
    return res;
}

Miller-Rabin素性测试(大数判质数)

  • 用于1e18级别的大数判质数
  • 是一种随机化/确定性算法,比试除法快得多
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//常见模板，64位确定版
long long mulmod(long long a, long long b, long long mod) {
    __int128 res = (__int128)a * b % mod;
    return (long long)res;
}

long long powmod(long long a, long long e, long long mod) {
    long long res = 1;
    while (e) {
        if (e & 1) res = mulmod(res, a, mod);
        a = mulmod(a, a, mod);
        e >>= 1;
    }
    return res;
}

bool isPrime(long long n) {
    if (n < 2) return false;
    for (long long p : {2,3,5,7,11,13,17,19,23,29,31,37}) {
        if (n%p == 0) return n==p;
    }
    long long d = n-1, s = 0;
    while ((d & 1) == 0) d >>= 1, s++;
    auto check = [&](long long a) {
        long long x = powmod(a, d, n);
        if (x == 1 || x == n-1) return true;
        for (int r = 1; r < s; r++) {
            x = mulmod(x, x, n);
            if (x == n-1) return true;
        }
        return false;
    };
    for (long long a : {2,325,9375,28178,450775,9780504,1795265022})
        if (a % n && !check(a)) return false;
    return true;
}