质因数分解

题目描述

已知正整数 $n$ 是两个不同质数的乘积（ $6 \le n \le 2 \times 10^9$ ），求较大的那个质数。输入一行一个 $n$ ，输出一行较大的质数。样例输入 21，输出 7（ $21 = 3 \times 7$ ）。

思路

设 $n = p \cdot q$ 且 $p < q$ ，则必有 $p < \sqrt{n}$ ：否则 $p, q$ 都大于 $\sqrt{n}$ ，乘积会超过 $n$ 。于是从小到大枚举 $d = 2, 3, \dots, \lfloor\sqrt{n}\rfloor$ ，第一个整除 $n$ 的 $d$ 就是较小的质数 $p$ （若 $d$ 是合数，它必有更小的因子也整除 $n$ ，与“第一个”矛盾），输出 $n / p$ 即可，复杂度 $O(\sqrt{n})$ 。

参考代码

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-29 18:39
# update_at: 2026-09-29 18:39

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    # 两个不同质数相乘，较小的那个必定 ≤ sqrt(n)，
    # 从小到大试除，找到的第一个因子就是较小质数。
    p = next(d for d in range(2, int(n**0.5) + 1) if n % d == 0)

    print(n // p)  # 较大质数 = n / 较小质数


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
29/**
 * 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-05 00:59
 * update_at: 2026-10-05 00:59
 */
// main.cpp：试除法求较大的质因子。
// n = p*q 且 p<q 为两个不同质数，从小到大第一个整除 n 的 d 就是 p，答案 n/p。
#include <iostream>

typedef long long ll;

int main() {
    ll n;
    std::cin >> n;

    // p < sqrt(n) < q，枚举到 sqrt(n) 即可；找到的第一个因子必为较小质数 p。
    for (ll d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            std::cout << n / d << std::endl;
            return 0;
        }
    }

    // 理论上 n 至少含两个不同质因子，不会走到这里。
    std::cout << 1 << std::endl;
    return 0;
}

目录

题目描述

思路

参考代码