[NOIP2012-普及] 质因数分解

题目描述

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

思路

设 $n = p \cdot q$ （ $p < q$ ），则 $p < \sqrt n < q$ ：从小到大试除，第一个能整除 $n$ 的 $d$ 就是最小质因数 $p$ ，直接输出商 $n / d$ 即答案。试除上界用 $d \cdot d \leqslant n$ 判断，最多约 44722 次， $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
24
25
26
27
28
29#!/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-02 09:40
# update_at: 2026-10-02 09:40

import sys


def smallest_factor(n: int) -> int:
    """试除找 n 的最小质因数：n 最多两个不同质因子，试到 √n 必然命中一个。"""
    d = 2
    while d * d <= n:
        if n % d == 0:
            return d
        d += 1 if d == 2 else 2  # 除 2 之后只需试奇数
    return n  # 兜底：n 本身是质数（题目保证不会走到这里）


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    p = smallest_factor(n)  # 最小的那个质因数
    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/**
 * 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 14:54
 * update_at: 2026-10-06 14:54
 */
#include <cstdio>

typedef long long ll;

ll n; // 题目给的数，n = p * q（p < q，均为质数）

int main() {
    scanf("%lld", &n);
    // 从小到大试除：第一个能整除 n 的 d 一定是最小质因数 p，
    // 且 p <= sqrt(n) < q，所以商 n / d 就是较大的质数 q
    for (ll d = 2; d * d <= n; d++) {
        if (n % d == 0) {
            printf("%lld\n", n / d);
            return 0;
        }
    }
    // 题目保证 n 是两个不同质数之积，不会走到这里
    return 0;
}

[NOIP2012-普及] 质因数分解

目录

题目描述

思路

参考代码