【GESP/CSP练习】GESP五级 / CSP-J 题解：luogu-P1075 [NOIP2012 普及组] 质因数分解

NOIP 2012 普及组第一题，洛谷 P1075。本题是算法竞赛与等级考试中极为经典的初等数论与质因数分解启蒙代表作，标准收录于 CCF GESP 五级考纲（初等数论：质数判定、因数分解与欧几里得算法考点）以及 CSP-J 普及组数论基础必做题单。题目核心考察如何利用正整数唯一分解定理与因数成对对称分布规律，避开低效盲目枚举，仅通过单层循环试除较小因数便能以 $\mathcal{O}(\sqrt{n})$ 的高效率瞬时求出较大质因子。题目难度⭐☆☆☆☆，洛谷难度等级评定为普及-。

luogu-P1075 [NOIP2012 普及组] 质因数分解

🔗 洛谷原题传送门：luogu-P1075 [NOIP2012 普及组] 质因数分解

题目描述

已知正整数 $n$ 是两个不同的质数的乘积，试求出两者中较大的那个质数。

输入格式

输入一个正整数 $n$。

输出格式

输出一个正整数 $p$，即较大的那个质数。

输入输出样例

输入 #1

121

输出 #1

17

说明/提示

$1 \le n\le 2\times 10^9$。

NOIP 2012 普及组 第一题

题目深度剖析

1. 数学本质与题设条件转化

题目明确指出了输入数据 $n$ 的核心代数特征：

• 正整数 $n$ 是两个不同质数的乘积，即： $n = p \times q \quad (p \ne q，且\ p, q \in \mathbb{P})$
• 我们的目标是求出两者中较大的那个质数，不妨设 $2 \le p < q$，则待求答案即为 $q$。

根据初等数论中的算术基本定理（唯一分解定理），任何大于 $1$ 的自然数都可以唯一分解为有限个质数的乘积。在本题中，$n$ 的质因数分解形式极其特殊，恰好仅有两个质因子 $p$ 与 $q$。

这也意味着，正整数 $n$ 的全部正因数集合是完全确定的，只有且仅有以下 $4$ 个数： $\operatorname{Div}(n) = \{ 1, p, q, n \}$

2. 因数对称性与试除上界推导

在自然数的因数分解中，因数总是成对出现的。 因为 $n = p \times q$ 且 $p < q$，我们可以通过反证法推导出较小因数 $p$ 的取值上界：

• 若假定 $p \ge \sqrt{n}$，由于 $q > p$，则必有 $q > \sqrt{n}$；
• 两式相乘得到 $p \times q > \sqrt{n} \times \sqrt{n} = n$，这与题设 $p \times q = n$ 产生不可调和的矛盾！
• 因此，较小的质因数 $p$ 必然严格满足： $2 \le p < \sqrt{n}$ 对应地，较大的质因数 $q$ 必然严格满足： $q = \frac{n}{p} > \sqrt{n}$

题目给定的数据范围为 $1 \le n \le 2 \times 10^9$： $\sqrt{n} \le \sqrt{2 \times 10^9} \approx 44721.36$ 也就是说，较小的那个质数 $p$ 的取值范围最大绝对不会超过 $44721$！

3. 为什么“找到的第一个因数一定是质数”？

许多初学者会产生一个疑问：我们在代码中直接从小到大枚举整数 $i$，如果 $n$ 能够整除 $i$，我们怎么能够保证这个 $i$ 一定是质数，而不是某个合数呢？

我们可以用初等数论中的经典反证法进行严格论证：

1. 我们从 $i = 2$ 开始递增枚举，假设第一个能够整除 $n$ 的整数是 $i_0$；
2. 假设 $i_0$ 是一个合数，那么根据合数的定义，$i_0$ 必然存在一个严格介于 $1$ 和 $i_0$ 之间的质因子 $d$（即 $1 < d < i_0$ 且 $d \mid i_0$）；
3. 因为 $d \mid i_0$ 且 $i_0 \mid n$，根据整除的传递性，必然有 $d \mid n$；
4. 然而，$d < i_0$，且我们在循环中是从小到大依次枚举所有因数的；如果存在 $d \mid n$，循环在枚举到 $d$ 时就已经命中并返回了，绝不可能越过 $d$ 而先在 $i_0$ 处第一次整除 $n$！
5. 这一矛盾证明：任何大于 $1$ 的合数，其能够被整除的最小因数必然是质数。

再结合前面推导出的结论：$n$ 大于 $1$ 的因数只有 $p, q, n$，且 $p < q < n$。因此，从 $2$ 开始从小到大遇到的第一个因数，必然且只能是质数 $p$！

由此得出极其优雅的算法设计：

• 我们根本不需要单独编写质数判定函数（如 isPrime()），也无需预先打表质数筛；
• 只要在单层循环中试除找到第一个因数 $i$，直接计算 $\frac{n}{i}$ 即为较大质数 $q$，立即输出并终止程序！

4. 算法演进与考场博弈对比

在 CCF GESP 五级和 CSP-J 考场中，面对本题有几种常见的实现思路对比：

可以看出，从较小端切入求解，利用代数关系 $\frac{n}{i}$ 转化求较大端，是初等数论中最核心的“对称化简思维”。

5. 数据规模与整型溢出避坑点

1. 循环判断条件的溢出隐患：

   • 题目给定 $n \le 2 \times 10^9$；
   • 32 位有符号整型 int 的上限为 $2^{31} - 1 = 2147483647 \approx 2.14 \times 10^9$；
   • 若将循环变量 $i$ 声明为 int，并写作 for (int i = 2; i * i <= n; ++i)： 当 $i$ 递增到 $46341$ 附近时，$i \times i \approx 2.147 \times 10^9$ 会直接超出 32 位有符号整型的表示范围，发生有符号整型溢出（Integer Overflow）！在 C++ 标准中这属于未定义行为（Undefined Behavior），通常会导致计算结果变为负数，使循环陷入不可控的死循环。
   • 安全规范解法：统一使用 64 位长整型 long long 存储变量 $n$ 与循环变量 $i$，彻底杜绝乘法溢出。

2. 遵循 CCF GESP 官方大纲规范：

   • 严禁在机考中引入不必要的复杂快读样板；
   • 严禁使用局部变长数组（VLA）；
   • 代码风格保持干净、通透与结构化。

完整参考代码 (C++11)

1/**
2 * Problem: luogu-P1075 [NOIP2012 普及组] 质因数分解
3 * Algorithm: 初等数论 / 因数分解 (Prime Factorization)
4 * Standard: C++11 (CCF GESP 官方大纲规范)
5 * Author: OneCoder
6 */
7
8#include <iostream>
9
10using namespace std;
11
12int main() {
13    // 读入正整数 n (数据规模保证 1 <= n <= 2 * 10^9)
14    // 采用 64 位长整型 long long 存储，避免因 i * i 运算超出 32 位整型上限而导致溢出死循环
15    long long n;
16    cin >> n;
17
18    // 根据初等数论与正整数唯一分解定理：
19    // n 是两个不同质数 p 和 q 的乘积 (设 2 <= p < q)
20    // 根据因数成对分布的对称性，较小的质数 p 必然满足：p <= sqrt(n)
21    // 且 n 仅有 1, p, q, n 这 4 个因数
22    // 任何大于 1 且能整除 n 的最小正整数，必然就是较小的质数 p
23    // 因此从 i = 2 开始自小到大枚举因数
24    for (long long i = 2; i * i <= n; ++i) {
25        if (n % i == 0) {
26            // 找到较小的质因数 i (即 p)
27            // 则较大的质因数必然等于 n / i (即 q)
28            // 直接输出较大的质数并结束程序
29            cout << n / i << endl;
30            return 0;
31        }
32    }
33
34    return 0;
35}