自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 21:14:35，当前版本为作者最后更新于2018-04-05 21:32:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
  }
}