质数(素数)和合数的定义

大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。

质数的判定：试除法

此处，给出常规代码写法

1
2
3
4
5
6
7
8
9
10
11
bool is_prime(int n){
    // 如果这个自然数比2小，则一定不是质数
    if(n < 2) return false;
    // 试除法
    for(int i = 2; i <= n; i++)
        // 能够被其它自然数整除，不是质数
        if(n % i == 0)
            return false;
    
    return true;
}

上述代码时间复杂度是O(n)。可是还能优化

例如：n = 12；i = 2; 那么 (n / i) 一定能整除 n。

12试除法试到2的时候同时可以知道6也是一个约数。

所以每次枚举的时候，只需要枚举较小的那个约数就行。

也就是说，只要 i <= (n / i)

下面给出优化过后的代码

1
2
3
4
5
6
7
8
9
10
11
bool is_prime(int n){
    // 如果这个自然数比2小，则一定不是质数
    if(n < 2) return false;
    // 优化过后的试除法
    for(int i = 2; i <= n / i; i++)
        // 能够被其它自然数整除，不是质数
        if(n % i == 0)
            return false;
    
    return true;
}

上述代码时间复杂度是O(n1/2)

主要修改了for循环里面的判断条件，没有使用sqrt函数，也没有使用i * i <= n，而是使用了i <= n / i。

因为使用sqrt函数慢，i * i 有爆 int 的可能

分解质因数：试除法

合数可以分解质因数，质数不能分解质因数，因为质数只能等于1乘本身这种形式，而1不是质数。

算数基本定理 也叫 唯一分解定理，主要的内容为：任何大于 1 的正整数都能 唯一 的分解为有限个质数的乘积。根据这一定理任何一个合数都可以被分解成几个质数相乘的形式。

质因数，给几个例子理解一下。

  • 1没有质因子。
  • 5只有1个质因子，5本身。（5是质数）
  • 6的质因子是2和3。(6 = 2 × 3)
  • 2、4、8、16等只有1个质因子：2。（2是质数，4 =2²，8 = 2³，如此类推）
  • 10有2个质因子：2和5。(10 = 2 × 5)

如何计算质因数：短除法

image-20230331225037221

代码模拟如上操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void divide(int n){
    // 枚举质因子（i一定是质数，可证明）
    for(int i = 2; i <= n / i; i++){
        // 如果i是质因子
        if(n % i == 0){
            // 进行计数
            int s = 0;
            while(n % i == 0){
                n /= i;
                s++;
            }
            // 输出底数和计数结果
            printf("%d %d\n", i, s);
        }
    }
    // n中最多只含有一个大于sqrt(n)的因子(可证明)
    if(n > 1) printf("%d %d\n", n, 1);
    puts("");
}

需要注意的点：

假如 i 是一个合数，那么它一定可以分解成多个质因子相乘的形式，这多个质因子同时也是 n 的质因子且比 i 要小，而比 i 小的数在之前的循环过程中一定是被条件除完了的，所以 i 不可能是合数，只可能是质数。
n中最多只含有一个大于sqrt(n)的因子，证明通过反证法：如果有两个大于sqrt(n)的因子，那么相乘会大于n，矛盾。

质数筛

埃氏筛法：

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

int primes[N], cnt;
bool st[N];

// 埃氏筛法
void get_primes(int n){
    for(int i = 2; i <= n; i++){
        // 如果被筛过了
        if(st[i]) continue;
        
        // 没有被筛过，当前数是质数
        primes[cnt ++] = i;
        // 只标记质数的倍数
        for(int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

int main()
{
    int n;
    cin >> n;
    
    get_primes(n);
    
    cout << cnt << endl;
    
    return 0;
}
时间复杂度：O(nlog(logn))

线性筛法（欧拉筛）：

线性筛法是对朴素筛法的进一步优化，埃式筛法的缺陷在于，对于同一个合数，可能被筛选多次。为了确保每一个合数只被筛选一次，我们用每个合数的最小质因子来进行筛选

之所以被称为线性，是因为：1 ~ n 之内的任何一个合数一定会被筛掉,而且筛的时候只用最小质因子来筛,每一个数都只有一个最小质因子,所以每个数都只会被筛一次,因此线性筛法是线性的.

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

int primes[N], cnt;
bool st[N];

// 欧拉筛
void get_primes(int n){
    for (int i = 2; i <= n; i ++ ){
        // 如果没被筛过，它是质数
        if (!st[i]) primes[cnt ++ ] = i;
        // 枚举质数表里面所有的质数(表里面的质数是从小到大存储的)
        for (int j = 0; primes[j] <= n / i; j ++ ){
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int n;
    cin >> n;
    
    get_primes(n);
    
    cout << cnt << endl;
    
    return 0;
}

时间复杂度：O(n)


1、因为primes中质数是递增的，所以如果i%primes[j]!=0代表i的最小质因数还没有找到，即prime[j]小于i的最小质因数。但并不妨碍，primes[j]是primes[j] * i的最小质因数。
2、如果当i%prime[j]==0时，代表i的最小质因数是prime[j]，primes[j]是primes[j] * i的最小质因数。
3、综上所述达到了每个数仅筛一次的效果，时间复杂度O ( n ) .