算法基础课笔记整理

1.质数的定义

在大于 $1$ 的整数中，如果只存在 $1$ 和它本身两个因子，则称这个数为质数（或素数）

2.试除法判断质数

非常简单，这里不多赘述。

#include <iostream>
#include <algorithm>

using namespace std;

int n, t;

bool is_prime(int x) {
    if (x <= 1) return false;
    for (int i = 2; i <= x / i; i ++) {
        if (x % i == 0) return false;
    }

    return true;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> t;
        if (is_prime(t)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}

时间复杂度：严格 $O(\sqrt{n})$

3.分解质因数

还是试除法。

这里有一个很重要的知识点——唯一分解定律：任意一个大于 $1$ 的整数 $x$ 都能唯一分解为 $x = p_1^{a_1} \times p_2^{a_2} \times … \times p_n^{a_n}$ （其中 $p$ 是质数）。

从 $2$ 开始枚举，如果当前枚举到的数 $i$ 能整除 $x$ ，那么说明 $i$ 是 $x$ 的一个质因子，然后枚举 $i$ 的次数。

注意一个性质：枚举到的能整除 $x$ 的数一定是质数。

证明：
假设某一时刻枚举到的 $x$ 的因数 $i$ 是一个合数。

那么一定有 $i = a \times b$ ，也就是说，$a$ 和 $b$ 也是 $x$ 的因数，且 $a,b < i$ 。

那么当枚举到 $a$ 时， $x$ 所有 $a$ 的正整数次幂因子都已经除尽，所以 $i$ 不能 $a$ 的正整数倍。

所以假设不成立。

优化

还有一个非常重要的性质：任意一个大于等于 $1$ 的整数 $x$ 最多有一个大于 $\sqrt{x}$ 的质因子。（很好证明，不多赘述）

#include <iostream>
#include <algorithm>

using namespace std;

int n, t;

void divide(int x) {
    for (int i = 2; i <= x / i; i ++) {
        if (x % i == 0) {
            int sum = 0;
            while (!(x % i)) {
                x /= i;
                sum ++;
            }
            cout << i << ' ' << sum << endl;
        }
    }

    if (x > 1) cout << x << ' ' << 1 << endl;

    return;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> t;
        divide(t);
        cout << endl;
    }

    return 0;
}

时间复杂度：最好 $O(\log{n})$ 最差 $O(\sqrt{n})$

4.筛质数

1.朴素筛

遍历 $2-n$ 范围内的所有数，将其所有倍数标记为合数，则剩下的就是质数。

证明：
假设我们遍历到了 $p$ ，且 $p$ 没有被标记，则说明从 $2$ 到 $p-1$ 范围内不存在 $p$ 的因数，所以 $p$ 是一个质数。

void count_primes(int x) {
    for (int i = 2; i <= x; i ++) {
        if (!st[i]) {
            ans ++;
        }
        for (int j = i + i; j <= x; j += i) st[j] = true;
    }

    return;
}

时间复杂度： $O(n \log n)$

2.埃氏筛

在朴素筛法中，我们可以只把质数的倍数筛去。根据上面说过的唯一分解定律，很容易证明这是正确的。

void count_primes_eratos(int x) {
    for (int i = 2; i <= x; i ++) {
        if (!st[i]) {
            ans ++;
            for (int j = i + i; j <= x; j += i) st[j] = true;
        }
    }

    return;
}

时间复杂度：$O(n \log \log n)$

3.欧拉筛（线性筛）

欧拉筛是对埃氏筛的优化，其基本思想是，对于每一个合数，我们只用其最小质因子筛掉它。

根据唯一分解定律，按照欧拉筛的思想，每一个合数一定会被筛掉。

那么我们剩下的问题就是：如何保证每个合数只被其最小质因子筛掉。

先看代码：

int count_primes_euler() {
    for (int i = 2; i <= n; i ++) {
        if (!st[i]) primes.push_back(i);

        for (int j = 0; primes[j] <= n / i; j ++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }

    return primes.size();
}

这里的关键是：if (i % primes[j] == 0) break;。

由于我们是从小到大遍历的质数表，所以第一次if成立时 $primes[j]$ 一定是 $i$ 的最小质因子，根据唯一分解定律，其一定也是 $primes[j] \times i$ 的最小质因子。

此时如果我们继续循环，同理根据唯一分解定律，后面遍历到的质数一定不是 $i$ 的最小质因子。所以此时我们终止循环。

至于primes[j] <= n / i，可以看作是primes[j] * i <= n，也就是越界判定。但为了避免乘法爆int上限，采用除法运算避免。