约定

  • 下文代码中 lint 代表 long long。
  • 下文代码中 pll代表 std::pair<lint, lint>。

质数

试除法判定质数

引理 1：∀ x ∈ {ℤ ∖ ℙ}，必然 ，使得 u ∣ x。

引理 1 证明：

假设 使得 u ∣ x。

因为 x 为合数，那么必然存在整数 使得 u ∣ x。

那么令 ，则 u ∣ x，且 ​，所以假设不成立。

故 ∀ x ∈ {ℤ ∖ ℙ}，必然 ，使得 u ∣ x。

那么可以遍历 ​ 间的所有整数，判断是否可以。

时间复杂度为 。

1
2
3
4
5
6
bool if_prime(lint x) { // 如果 x 为质数，返回 true；否则返回 false
  if (x < 2) return false;
  for (lint 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
12
// 对 x 分解质因数，返回 std::vector<pll>，每一个元素 first 为底数，second 为指数
auto get_prime_factor(lint x) {
  std::vector<pll> res;
  for (lint i = 2, cnt; i <= x / i; ++i) {
    if (x % i) continue;
    cnt = 0;
    while (x % i == 0) x /= i, ++cnt;
    res.push_back({i, cnt});
  }
  if (x > 1) res.push_back({x, 1});
  return res;
}

质数筛

时间复杂度为 O(n)。

1
2
3
4
5
6
7
8
9
// 范围 [1,n] 中所有质数
auto get_prime(int n) {
  std::vector<int> res;
  std::vector
  
  for (int i = 2; i <= n; ++i) {
    
  }
}