「初等数论初步」素数及其判别法

发表于 | 分类于

素数：仅有两个正因数的正整数，即为正因数只有1和本身的数，也称质数

合数：不是素数又不是1的正整数

  • 1既不是素数(只有一个正因子)，也不是合数.
  • 2是唯一的偶素数，也是最小的素数.

我们发现，每个正整数x除1外的最小正因数p是一个素数

证明：如果p不是一个素数的话，那么p必定有除1、p以外的正因数q，使得 q|p, 那么q|x, 那么q是x的比p小的正因数，所以p就不是x的最小正因数了，与已知矛盾.

判断一个数x是不是素数，只需要判断到sqrt(x)即可，因为如果x是一个合数，那么在（1, sqrt(x)]中的因数q，一定有一个[sqrt(x), x）中的因数p与其对应，使得p*q == n，且sqrt(x)^2 == n;

如果大于1的整数a不能被所有不超过sqrt(a)的素数整除, 那么a一定是素数.

所以用代码判定一个数是不是素数：

1
2
3
4
5
6
7
//试除法 O(根号n)
bool primer(int n) {
    for(int i = 2; i <= sqrt(n); i++) {
        if(n % i == 0) return false;
    }
    return true;
}

埃拉托斯特尼（Eratosthenes）筛法–埃筛

例题：找出1~100以内的全部素数.

做法：只需要把1~100以内的合数去掉即可，对于1~100以内的每个合数，他一定能被某个不超过sqrt(x)的整数整除，从而能被不超过sqrt(100) = 10的整数整除。我们只需要把不超过10的素数（2， 3， 5， 7）除其本身以外的倍数以及1去掉，剩下的就是不超过100的全部素数。这种寻求素数的方法叫做埃拉托斯特尼(Eratosthenes)筛法即 埃筛.

先找sqrt(n)以内的素数，然后倍数增长标记.

附上埃筛代码：

1
2
3
4
5
6
7
8
9
10
11
12
//埃筛 O(NloglogN) 接近线性
bool v[n_max + 1];
void primer(int n) {
    memset(v, 0, sizeof(v));
    for(int i = 2; i <= n; i++) {
        if(v[i]) continue;
        printf("%d ", i);
        for(int j = i; j <= n/i; j++) {
            v[i*j] = 1;
        }
    }
}

线性筛法
线性筛法是一种O(n)的算法，但是代码复杂度较高，不易考场书写，其实埃筛就已经完全够用，它已经接近线性了，所以考场书写推荐埃筛！这里就不进行线性筛法的讲解了，有兴趣的同学可以自行网上搜索学习，附上代码吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//线性筛法 O(n) 写法较难 用埃筛就可以了
int v[N_MAX], prime[N_MAX];
void primer(int n) {
    memset(v, 0, sizeof(v)); //最小质因子;
    m = 0; //质数数量;
    for(int i = 2; i <= n; i++) {
        if(v[i] == 0) {v[i] == i; prime[++m] = i;}
        for(int j = 1; j <= m; j++) {
            if(prime[j] > v[i] || prime[j] > n/i) break;
            v[i * prime[j]] = prime[j];
        }
    }
    for(int i = 1; i <= m; i++) printf("%d\n", prime[i]);
}