B3715 分解质因子 2

· · 题解

B3715 分解质因子 2

Analysis

唯一分解定理：对任意大于 1 的正整数 n，设 n 的质因子分别为 p_1, p_2, \dots p_k，则 n 一定能分解为上述质因子若干次幂的乘积，即 n = p_1^{c_1} p_2^{c_2} \dots p_k^{c_k}。并且这种分解方式是唯一的，也就是不存在另一种分解方式使得对应质因子的指数不同。

引理：对任意大于 1 的正整数 n，n 至多有一个大于 \sqrt n 的质因子。假设该质因子存在，它在唯一分解式中的指数一定是 1。

证明：

  1. 假设 n 有两个大于 \sqrt n 的质因子 p, q，写出 n 的唯一分解式 n = t p q > t \sqrt n \sqrt n = tn，其中 t \geq 1。得 n > tn，矛盾。这就证明了至多只有一个大于 \sqrt n 的质因子。
  2. 在上式中取 p = q，矛盾仍成立。这就证明了若唯一大于 \sqrt n 的质因子存在，则它在唯一分解式中的指数一定是 1。

质因子分解：根据上述引理，只需要枚举 i = 2 \sim \sqrt n，通过试除可以求出 n 所有小于 \sqrt n 的质因子。在 n 除掉这些质因子后如果不为 1，则剩下的数就是那个大于 \sqrt n 的质因子。对于一次查询，时间复杂度 O(\sqrt n)。

Code

#include <iostream>

int main() {
  int T;
  for (std::cin >> T; T; --T) {
    long long n; std::cin >> n;
    long long m = n;
    for (int i = 2; 1ll * i * i <= n; ++i) while (m % i == 0) {
      m /= i;
      std::cout << i << ' ';
    }
    if (m != 1) {
      std::cout << m;
    }
    std::cout << std::endl;
  }
}