「一本通 6.2 练习 1」质因数分解

题目描述

给定正整数 $n = p \cdot q$ （ $p, q$ 为不同质数），求 $\max(p, q)$ 。

思路

两个质因数中小的那个必不超过 $\sqrt n$ （否则乘积超过 $n$ ），从小到大试除 $2 \sim \lfloor\sqrt n\rfloor$ ，第一个整除 $n$ 的 $d$ 对应的商 $n/d$ 就是较大的质因数。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23#!/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-09-30 22:30
# update_at: 2026-09-30 22:30

import sys
from math import isqrt


def solve() -> None:
    n = int(sys.stdin.buffer.read())

    # 设 n = p*q 且 p < q，则 p ≤ √n（否则 p*q > √n*√n = n 矛盾），
    # 所以最小质因子一定落在 [2, ⌊√n⌋] 内，从小到大试除到它即可。
    # 命中的第一个 d 必是质数：若 d 是合数，它的质因子更小、早就把 n 除尽了。
    p = next(d for d in range(2, isqrt(n) + 1) if n % d == 0)
    print(n // p)  # 商就是较大的那个质数


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28/**
 * 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-06 01:19
 * update_at: 2026-10-06 01:19
 */
#include <cstdio>

typedef long long ll;

ll n; // 输入的整数，是两个不同质数的乘积

// 试除找到较小的质因数，返回较大的那个质数
ll solve(ll x) {
    for (ll d = 2; d * d <= x; ++d) { // 较小质因数不超过 sqrt(x)
        if (x % d == 0) {
            return x / d; // d 是小质因数，x/d 是大质因数
        }
    }
    return x; // 兜底，理论上不会发生
}

int main() {
    scanf("%lld", &n);
    printf("%lld\n", solve(n));
    return 0;
}

「一本通 6.2 练习 1」质因数分解

目录

题目描述

思路

参考代码