题解 | #分解质因数#

题目链接

HIGH4 分解质因数

题目描述

输入一个正整数 n，请对它进行质因数分解，并从小到大输出它的所有质因子，两个因子之间用空格隔开。如果一个质因子出现了多次，则需要重复输出。

解题思路

这是一个经典的质因数分解问题。核心思想是使用试除法，不断地用最小的质数去除给定的数 n，直到 n 变为 1。

从最小的质数开始：我们从最小的质数 2 开始尝试整除 n。
循环整除：对于当前的质数 i（从2开始）：
- 使用一个 while 循环，判断 n 是否能被 i 整除（即 n % i == 0）。
- 如果可以，说明 i 是 n 的一个质因子。我们输出 i，然后更新 n 为 n / i，以消除这个因子。
- 继续这个 while 循环，直到 n 不再能被当前的 i 整除。这可以确保我们找出所有重复的质因子（例如，12 中的两个 2）。
递增试除数：当 n 不能再被当前的 i 整除后，我们将 i 增加 1，然后重复步骤 2。
优化循环上界：我们不需要一直将 i 增加到 n。一个重要的优化是，试除的因子 i 只需要检查到 sqrt(n) 即可。
- 原理：如果一个数 n 不是质数，那么它至少有一个小于或等于 sqrt(n) 的质因子。如果我们在 [2, sqrt(n)] 的范围内都找不到 n 的任何因子，那么 n 本身就是一个质数。
- 所以，我们的主循环可以写成 for (int i = 2; i * i <= n; ++i)。
处理剩余的数：在上面的循环结束后，如果 n 的值仍然大于 1，说明剩下的 n 本身就是一个大于 sqrt(n) 的质因子。我们需要将这个最后的质因子也输出。

综上，算法流程为：

从 i = 2 开始循环，直到 i*i > n。
在循环内，用一个 while 循环找出所有等于 i 的质因子。
循环结束后，如果 n > 1，则剩下的 n 也是一个质因子，输出它。

代码

cpp
java
python

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n;
    cin >> n;

    for (long long i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            cout << i << " ";
            n /= i;
        }
    }

    if (n > 1) {
        cout << n << " ";
    }
    cout << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();

        for (long i = 2; i * i <= n; i++) {
            while (n % i == 0) {
                System.out.print(i + " ");
                n /= i;
            }
        }

        if (n > 1) {
            System.out.print(n + " ");
        }
        System.out.println();
    }
}

n = int(input())

i = 2
result = []
while i * i <= n:
    while n % i == 0:
        result.append(str(i))
        n //= i
    i += 1

if n > 1:
    result.append(str(n))

print(" ".join(result) + " ")

算法及复杂度

算法：试除法、质因数分解
时间复杂度： $\mathcal{O}(\sqrt{n})$ 。最坏情况是 n 为一个大质数，此时外层循环会执行大约 $\sqrt{n}$ 次。
空间复杂度： $\mathcal{O}(1)$ 。我们只需要常数级别的额外空间来存储变量。（Python版本使用了列表，空间复杂度为 $\mathcal{O}(\log n)$ ，因为一个数的质因子数量不会很多）。