试除法判定素数

1
2
3
4
5
6
7
8
bool is_prime(int x) {
    if(x < 2)	return false;
    for(int i = 2; i <= x / i; i++) {
        if(x % i == 0)
            return false;
    }
    return true;
}

朴素筛法求素数

合数有被重复筛除的情况

1
2
3
4
5
6
7
8
9
10
11
int primes[N], cnt;	//primes[]存储所有素数
bool st[N];	//st[x]存储x是否被筛过

void get_primes(int n) {
    for(int i = 2; i <= n; i++) {
        if(st[i])	continue;
        primes[cnt++] = i;
        for(int j = i; j <= n; j += i)
            st[j] = true;
    }
}

线性筛法求素数

原理：用一个合数的最小质因子来筛掉这个合数，合数只被筛一次

1
2
3
4
5
6
7
8
9
10
11
12
13
int primes[N], cnt;	//primes[]存储所有素数
bool st[N];	//st[x]存储x是否被筛过

void get_primes(int n) {
    for(int i = 2; i <= n; i++) {
        if(!st[i])	primes[cnt++] = i;
        //primes[j] * i <= n 转化为 primes[j] <= n / i
        for(int j = 0; primes[j] <= n / i; j++) {
            st[i * primes[j]] = true;	//primes[j] * i 为合数
            if(i % primes[j] == 0)	break;	//确保primes[j]是这个合数的最小质因子
        }
    }
}

我们来看break语句：

当i % primes[j] == 0时，如果没有break，则会开始筛除i * primes[j + 1]，取i / primes[j]值为x，那么，这个式子可以等价为x * primes[j] * primes[j + 1]，显然可以看出**primes[j]**才是最小质因子，这次的筛除不成立。

看一个具体的例子：

取n = 15

i 的取值 primes[j] == 2 primes[j] == 3
i = 2 2 * 2
i = 3 3 * 2 3 * 3
i = 4 4 * 2
i = 5 5 * 2 5 * 3
i = 6 6 * 2
i = 7 7 * 2

以i = 4为例，4 * 2被筛除，下一个为4 * 3，显然可以分解为6 * 2，2为最小质因子，所以不能在这里被筛除