526互联

第四讲 数学知识——质数

发布时间 2023-12-09 13:21:26作者: coldair7

AcWing 866. 试除法判定质数

时间复杂度 \(O(T \sqrt a)\)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
bool isprime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; ++i) {
        if (x % i == 0) return false;
    }
    return true;
}
int main()
{
    int T, a;
    cin >> T;
    while (T--) {
        cin >> a;
        puts(isprime(a) ? "Yes" : "No");
    }
    return 0;
}

AcWing 867. 分解质因数

时间复杂度 \(O(T \sqrt a)\)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    int T; cin >> T;
    while (T--) {
        int a; cin >> a;
        for (int i = 2; i <= a / i; ++i) {
            int cnt = 0;
            while (a % i == 0) {
                ++cnt;
                a /= i;
            }
            if (cnt) printf("%d %d\n", i, cnt);
        }
        if (a > 1) printf("%d 1\n", a);
        puts("");
    }
    return 0;
}

AcWing 868. 筛质数

埃式筛法：

时间复杂度 \(O(n\log_2\log_2n)\)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e6 + 10;
int cnt, n;
bool st[MAXN];
void init(int x) {
    for (int i = 2; i <= n; ++i) {
        if (st[i]) continue;
        ++cnt;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}
int main() {
    cin >> n; init(n);
    cout << cnt;
    return 0;
}

证明时间复杂度是 \(O(n\log_2\log_2n)\)

我们先假设 \(st_i\) 永远不是 true，对于每个枚举到 \(i\) 时的运算次数，是 \(\frac{n}{i}\) 那么整个时间复杂度大约就是

\[\begin{aligned} \sum \limits _ {i = 1} ^ n \frac{n}{i} &= n \sum \limits _ {i = 1} ^ n \frac{1}{i} \\ &= n \ln n \\ &= n \log _ e n \\ &\thickapprox n \log _ 2 n \end{aligned}\]

\(e\thickapprox 2.718281828459045\)

热知识：\(\log _ e n < \log _ 2 n , \ln n < \log_2n\)， \(1\) 到 \(n\) 中一共有 \(\frac{n}{\ln n}\) 个质数

我们现在把 \(st_i\) 永远不是 true 这个条件去掉，只有质数的时候枚举，也就是乘 \(\frac{1}{\ln n}\)

\[\begin{aligned} n\ln n\frac{1}{\ln n} &= n \ln\ln n \\ &\thickapprox n\log_2\log_2n\end{aligned} \]

证毕

线性筛法：

时间复杂度 \(O(n)\)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1e6 + 10;
int cnt, n, primes[MAXN];
bool st[MAXN];
void init(int x) {
    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() {
    cin >> n; init(n);
    cout << cnt;
    return 0;
}
  1. 证明线性筛法的正确性
  • 设 primes[j] 是 pj
  • 我们先分两种情况
  • 情况一 \((pj \mid i)\)
    • 那么 \(pj\) 一定是 \(i\) 的最小质因子
    • \(pj \times i\) 的数的最小质因子也就是 \(pj\) 了
  • 情况二 \((pj \nmid i)\)
    • \(pj \times i\) 这个数的最小质因子也就是 \(pj\) 了
  • 所有合数都被它的最小质因子筛掉，这做法也就对了。
    证毕
  1. 证明线性筛法的时间复杂度是 \(O(n)\)
  • 前面知道 \(1\) 到 \(n\) 中一共有 \(\frac{n}{\ln n}\) 个质数
  • 直接带进去之后约等于 \(O(n)\)