【例4.18】分解质因数

GitHub跳转原题关系图返回列表

利用从 2 到 √n 逐个试除的方法进行分解,若循环后剩余商大于 1,则其必为最后一个素因子。

OJ: roj

题目 ID: 5034

难度:入门

标签:试除法数学质数

创建: 2026-10-08 22:48

更新: 2026-10-08 22:48

形式化题目

给定一个正整数 nn(2≤n≤200002 \le n \le 20000),将其分解为若干个质因数连乘的形式,并按质因数从小到大的顺序输出。格式为 n=p1*p2*...*pk。

正解

思路

标准处理逻辑已经验证通过。

试除到 n\sqrt{n} 后,若剩余商 c>1c > 1,则 cc 必为素数(因为 cc 的最小质因子必 >n> \sqrt{n},否则它早被除尽了)。 注意:cc 不一定是 nn 的最大质因数,也不一定 >n> \sqrt{n} ——例如 n=19950=2⋅3⋅52⋅7⋅19n = 19950 = 2 \cdot 3 \cdot 5^2 \cdot 7 \cdot 19,最大质因数 19<1995019 < \sqrt{19950},但除尽 2,3,5,72,3,5,7 后剩余商恰为 19。准确地说:剩余商 >1> 1 ⟺ 最大质因数的指数恰为 1。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 22:40
# update_at: 2026-10-08 22:40

import sys
from collections.abc import Iterator


def prime_factors(n: int) -> Iterator[int]:
    """按从小到大产出 n 的全部质因子(含重复)。

    循环退出条件 d*d > n 说明 d 已试到 sqrt(n):此时若剩余商 > 1 而是合数,
    它的质因子 q <= sqrt(n) 早该被除尽,矛盾,故剩余商必为素数,补产出一次。
    """
    d = 2
    while d * d <= n:
        while n % d == 0:  # 除尽因子 d,重复因子逐个产出
            yield d
            n //= d
        d += 1
    if n > 1:              # 剩余商必为素数,补打最后一个质因子
        yield n


def solve() -> None:
    """读入 n,输出 "n=p1*p2*...*pk"。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data, None)
    if n is None:          # 空输入:不输出
        return
    print(f"{n}=" + "*".join(map(str, prime_factors(n))))


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-08 22:40
 * update_at: 2026-10-08 22:40
 */
// roj 5034《【例4.18】分解质因数》:从小到大试除 + 循环后补打剩余商(必为素数)
//
// 题意:输入正整数 n(2 <= n <= 20000),输出 "n=p1*p2*...*pk",
//   质因数(含重复)按从小到大排列。样例 36 -> "36=2*2*3*3"。
//
// 做法:i 从 2 起枚举,i*i <= n 时把 i 除尽(重复因子逐个输出)。
//   从小到大枚举保证命中的 i 一定是质数:若 i 是合数,它的更小质因子
//   早已被除尽,此时 n 不可能还被 i 整除。
//
// 为什么循环退出后「剩余商 c > 1 ⇒ c 是素数」:
//   若 c 是合数,则 c 有质因子 q 满足 q <= sqrt(c)。循环退出条件是 i*i > c,
//   而 i 是从 2 逐个递增到该条件的,所以 q 早就被枚举过;又因 q | c 且 q | 原 n,
//   枚举到 q 时内层 while 会把 n 中所有因子 q 除尽,c 里就不可能再留下 q,矛盾。
//   故 c 只能是 1 或素数,c > 1 时必须再输出一次,否则会漏掉最后一个质因子。
//
// 注意(易错):判断「要不要补打」不能写成「最大质因数 > sqrt(n)」。
//   例如 n = 19950 = 2*3*5*5*7*19,最大质因数 19 < sqrt(19950) ≈ 141.2,
//   但把 2,3,5,7 除尽后剩余商正是 19 > 1,必须补打。
//   准确的判据是:剩余商 > 1 当且仅当最大质因数的指数恰为 1。
//   题面只要求「质因数必须由小到大」,这层判断对素数输入(如 2、19997)同样正确。

#include <iostream>

using namespace std;

typedef long long ll;

// 从小到大试除分解 n,按升序输出 "n=p1*p2*...*pk"。
void solve() {
    ll n;
    if (!(cin >> n)) return; // 空输入:不输出任何东西

    cout << n << "=";
    bool first = true; // 还没输出过任何因子,用来决定乘号的位置

    for (ll i = 2; i * i <= n; i++) {
        while (n % i == 0) { // 除尽因子 i,重复因子按出现次数逐个输出
            if (!first) cout << "*";
            first = false;
            cout << i;
            n /= i;
        }
    }

    if (n > 1) { // 剩余商必为素数,补打最后一个质因子
        if (!first) cout << "*";
        cout << n;
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

复杂度

  • 时间复杂度:O(n)O(\sqrt{n})。
  • 空间复杂度:O(1)O(1)。

总结

  • 核心算法:从 2 试除到 n\sqrt n(动态递减)。循环结束后若剩余 >1>1 则补打。
  • 为什么「剩余商必为素数」:c>1c > 1 时,若 cc 有 ≤c\le \sqrt{c} 的因子,那它在循环中就已被除尽,矛盾。 ⚠ 常见误解指出:「剩余商 >1>1 ⇔ 最大质因数 >n> \sqrt n」是【错的】。如 n=19950n=19950,最大质因数 19<141.219 < 141.2,但除完后剩余商恰为 19 必须补打。正确判据是:剩余商 >1> 1 ⟺ 最大质因数的指数恰为 1。另外如 n=12=22⋅3n=12 = 2^2 \cdot 3,剩余商为 3 也是反例。
  • 缺失此分支的影响(V1 反事实):若删掉循环后「剩余 >1>1 则输出」分支,在 ROJ 数据集上会导致 6/10 点失败。
  • 素数输入问题:题面说「分解质因数只针对合数」,但测试数据实际包含 n=2n=2 等素数输入;程序自然处理输出 2=2 即可通过。
  • 验证强度:n=2..20000n = 2..20000 全 19999 个值穷举,主解试除 vs 异源 SPF 筛法链 0 分歧;V2 字面量集合仅包含 {0,1,2}。最坏点 n=19997n=19997 实测 8.3 ms。