题解 | #分解质因数#

题目链接

分解质因数

题目描述

给定一个正整数 $n$ ，请将 $n$ 按从小到大的顺序分解为若干个质因数并输出。

解题思路

本题要求对一个正整数 $n$ 进行质因数分解，我们可以使用试除法来解决。

具体步骤如下：

从最小的质数 $i = 2$ 开始，尝试看 $n$ 能否被 $i$ 整除。
如果 $n$ 能被 $i$ 整除，说明 $i$ 是 $n$ 的一个质因数。我们就输出 $i$ ，然后用 $n$ 除以 $i$ 来更新 $n$ 的值。我们重复这个过程，直到 $n$ 不能再被 $i$ 整除为止，这样可以处理掉所有等于 $i$ 的质因数。
让 $i$ 增加 1，继续对新的 $n$ 进行上述操作。
我们可以发现，当 $i$ 循环到 $\sqrt{n}$ 之后，如果 $n$ 仍然大于 1，那么剩下的 $n$ 一定是一个质数。这是因为如果剩下的 $n$ 是一个合数，那么它必然可以分解成两个因子的乘积，其中至少有一个因子会小于或等于 $\sqrt{n}$ ，而这个因子在之前的循环中就已经被除掉了。因此，循环结束后，如果 $n > 1$ ，我们直接输出 $n$ 即可。

例如，分解 18：

从 $i=2$ 开始，18 能被 2 整除，输出 2， $n$ 变为 9。
9 不能被 2 整除。
$i$ 变为 3，9 能被 3 整除，输出 3， $n$ 变为 3。
3 还能被 3 整除，输出 3， $n$ 变为 1。
循环结束，最终得到 2 3 3。

代码

cpp
java
python

#include <iostream>

using namespace std;

int main() {
    long long n; // 使用 long long 避免 n 溢出
    cin >> n;
    bool first = true; // 用于控制空格输出
    for (long long i = 2; i * i <= n; ++i) { // 使用 long long 避免 i*i 溢出
        while (n % i == 0) {
            if (!first) {
                cout << " ";
            }
            cout << i;
            first = false;
            n /= i;
        }
    }
    // 如果n最后还剩下大于1的数，那么它一定是一个质数
    if (n > 1) {
        if (!first) {
            cout << " ";
        }
        cout << n;
    }
    cout << "\n";
    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(); // 使用 long 避免 n 溢出
        boolean first = true; // 用于控制空格输出
        for (long i = 2; i * i <= n; ++i) { // 使用 long 避免 i*i 溢出
            while (n % i == 0) {
                if (!first) {
                    System.out.print(" ");
                }
                System.out.print(i);
                first = false;
                n /= i;
            }
        }
        // 如果n最后还剩下大于1的数，那么它一定是一个质数
        if (n > 1) {
            if (!first) {
                System.out.print(" ");
            }
            System.out.print(n);
        }
        System.out.println();
    }
}

n = int(input())
ans = []
i = 2
# 循环直到 i*i > n
while i * i <= n:
    # 如果 n 能被 i 整除，说明 i 是一个质因数
    while n % i == 0:
        ans.append(i)
        n //= i
    i += 1
# 如果最后 n 还大于 1，说明剩下的 n 也是一个质因数
if n > 1:
    ans.append(n)

# 将结果列表转换为字符串并用空格连接
print(*ans)

算法及复杂度

算法：试除法
时间复杂度： $O(\sqrt{n})$ ，其中 $n$ 是输入的整数。循环最多执行到 $\sqrt{n}$ 。
空间复杂度：对于 C++ 和 Java 实现，我们是直接输出，所以空间复杂度是 $O(1)$ 。对于 Python 实现，我们用一个列表来存储质因数，其长度最多为 $O(\log n)$ ，所以空间复杂度是 $O(\log n)$ 。