约定

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

质数

试除法判定质数

引理 1：$\forall\,x\in\{\mathbb{Z}\,\backslash\,\mathbb{P}\}$，必然 $\exists\,u\in\big\{[2,\left\lfloor\sqrt{x}\right\rfloor]\land \mathbb{Z}\big\}$，使得 $u\mid x$。

引理 1 证明：

假设 $\nexists u\in \big\{[2,\left\lfloor\sqrt{x}\right\rfloor]\land \mathbb{Z}\big\}$ 使得 $u\mid x$。

因为 $x$ 为合数，那么必然存在整数 $v\in\big(\lfloor\sqrt{x}\rfloor,n\big)$ 使得 $u\mid x$。

那么令 $u=\dfrac{x}{v}$，则 $u\mid x$，且 $u\in \big\{[2,\left\lfloor\sqrt{x}\right\rfloor]\land \mathbb{Z}\big\}$​，所以假设不成立。

故 $\forall\,x\in\{\mathbb{Z}\,\backslash\,\mathbb{P}\}$，必然 $\exists\,u\in\big\{[2,\left\lfloor\sqrt{x}\right\rfloor]\land \mathbb{Z}\big\}$，使得 $u\mid x$。

那么可以遍历 $[2,\lfloor\sqrt{x}\rfloor]$​ 间的所有整数，判断是否可以。

时间复杂度为 $O(\sqrt{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;
}

分解质因数

时间复杂度为 $O(\sqrt{x})$。

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) {
    
  }
}