NOIP 全国联赛真题
🎨 视觉封面【NOIP真题】2012 质因数分解 luogu-P1075 | 适用于 GESP五级 / CSP-J 练习
算术基本定理指出,任何大于 1 的自然数都能唯一分解为质数的乘积,而现代 RSA 等公钥密码学体系正是建立在大整数质因数分解的单向计算难度之上。洛谷 P1075 [NOIP2012 普及组]《质因数分解》以极度精炼的题目背景(已知 为两个不同质数的乘积,求较大质数),考察了数论试题中最具辨识度的试除优化思维。面对高达 的数据规模,盲目枚举必然超时;而利用合数的对称性与质数分布,只需 贪心试除找到最小质因数即可瞬间完成除法反推。这道题是 GESP 五级数论素养与边界优化的入门标杆。
luogu-P1075 [NOIP2012 普及组] 质因数分解
🔗 洛谷原题传送门:luogu-P1075 [NOIP2012 普及组] 质因数分解
题目描述
已知正整数 是两个不同的质数的乘积,试求出两者中较大的那个质数。
输入格式
输入一个正整数 。
输出格式
输出一个正整数 ,即较大的那个质数。
输入输出样例
输入 #1
21输出 #1
7说明/提示
。
NOIP 2012 普及组 第一题
题目深度剖析
1. 数学本质与题设条件转化
题目明确指出了输入数据 的核心代数特征:
- 正整数 是两个不同质数的乘积,即:
- 我们的目标是求出两者中较大的那个质数,不妨设 ,则待求答案即为 。
根据初等数论中的算术基本定理(唯一分解定理),任何大于 的自然数都可以唯一分解为有限个质数的乘积。在本题中, 的质因数分解形式极其特殊,恰好仅有两个质因子 与 。
这也意味着,正整数 的全部正因数集合是完全确定的,只有且仅有以下 个数:
2. 因数对称性与试除上界推导
在自然数的因数分解中,因数总是成对出现的。 因为 且 ,我们可以通过反证法推导出较小因数 的取值上界:
- 若假定 ,由于 ,则必有 ;
- 两式相乘得到 ,这与题设 产生不可调和的矛盾!
- 因此,较小的质因数 必然严格满足: 对应地,较大的质因数 必然严格满足:
题目给定的数据范围为 : 也就是说,较小的那个质数 的取值范围最大绝对不会超过 !
3. 为什么“找到的第一个因数一定是质数”?
许多初学者会产生一个疑问:我们在代码中直接从小到大枚举整数 ,如果 能够整除 ,我们怎么能够保证这个 一定是质数,而不是某个合数呢?
我们可以用初等数论中的经典反证法进行严格论证:
- 我们从 开始递增枚举,假设第一个能够整除 的整数是 ;
- 假设 是一个合数,那么根据合数的定义, 必然存在一个严格介于 和 之间的质因子 (即 且 );
- 因为 且 ,根据整除的传递性,必然有 ;
- 然而,,且我们在循环中是从小到大依次枚举所有因数的;如果存在 ,循环在枚举到 时就已经命中并返回了,绝不可能越过 而先在 处第一次整除 !
- 这一矛盾证明:任何大于 的合数,其能够被整除的最小因数必然是质数。
再结合前面推导出的结论: 大于 的因数只有 ,且 。因此,从 开始从小到大遇到的第一个因数,必然且只能是质数 !
由此得出极其优雅的算法设计:
- 我们根本不需要单独编写质数判定函数(如
isPrime()),也无需预先打表质数筛; - 只要在单层循环中试除找到第一个因数 ,直接计算 即为较大质数 ,立即输出并终止程序!
4. 算法演进与考场博弈对比
在 CCF GESP 五级和 CSP-J 考场中,面对本题有几种常见的实现思路对比:
| 算法方案 | 核心实现思路 | 时间复杂度 | 运算次数 () | 洛谷评测结果 |
|---|---|---|---|---|
| 反向暴力枚举 | 从 向下递减枚举 ,判断是否整除且为质数 | 最坏达 次运算 | ❌ 超时 TLE (仅得 60 分) | |
| 盲目预处理筛法 | 先开数组用埃氏筛/欧拉筛预处理质数表,再查找因数 | 空间与时间 | 数组需开到 ,爆内存 | ❌ 内存超限 MLE (空间爆 128MB) |
| 正向试除因数法 (最优解) | 从 到 递增枚举试除,命中立即输出 退出 | 最多仅需 次运算 | ✅ 最优解 100 分 AC (耗时 < 1ms) |
可以看出,从较小端切入求解,利用代数关系 转化求较大端,是初等数论中最核心的“对称化简思维”。
5. 数据规模与整型溢出避坑点
-
循环判断条件的溢出隐患:
- 题目给定 ;
- 32 位有符号整型
int的上限为 ; - 若将循环变量 声明为
int,并写作for (int i = 2; i * i <= n; ++i): 当 递增到 附近时, 会直接超出 32 位有符号整型的表示范围,发生有符号整型溢出(Integer Overflow)!在 C++ 标准中这属于未定义行为(Undefined Behavior),通常会导致计算结果变为负数,使循环陷入不可控的死循环。 - 安全规范解法:统一使用 64 位长整型
long long存储变量 与循环变量 ,彻底杜绝乘法溢出。
-
遵循 CCF GESP 官方大纲规范:
- 严禁在机考中引入不必要的复杂快读样板;
- 严禁使用局部变长数组(VLA);
- 代码风格保持干净、通透与结构化。
完整参考代码 (C++11)
/**
* Problem: luogu-P1075 [NOIP2012 普及组] 质因数分解
* Algorithm: 初等数论 / 因数分解 (Prime Factorization)
* Standard: C++11 (CCF GESP 官方大纲规范)
* Author: OneCoder
*/
#include <iostream>
using namespace std;
int main() {
// 读入正整数 n (数据规模保证 1 <= n <= 2 * 10^9)
// 采用 64 位长整型 long long 存储,避免因 i * i 运算超出 32 位整型上限而导致溢出死循环
long long n;
cin >> n;
// 根据初等数论与正整数唯一分解定理:
// n 是两个不同质数 p 和 q 的乘积 (设 2 <= p < q)
// 根据因数成对分布的对称性,较小的质数 p 必然满足:p <= sqrt(n)
// 且 n 仅有 1, p, q, n 这 4 个因数
// 任何大于 1 且能整除 n 的最小正整数,必然就是较小的质数 p
// 因此从 i = 2 开始自小到大枚举因数
for (long long i = 2; i * i <= n; ++i) {
if (n % i == 0) {
// 找到较小的质因数 i (即 p)
// 则较大的质因数必然等于 n / i (即 q)
// 直接输出较大的质数并结束程序
cout << n / i << endl;
return 0;
}
}
return 0;
}所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【NOIP真题】2001 最大公约数和最小公倍数问题 luogu-P1029 | 适用于 GESP五级 / CSP-J 练习
最大公约数(gcd)与最小公倍数(lcm)是初等数论中最对称、最优雅的一对孪生概念。洛谷 P1029 [NOIP2001 普及组]《最大公约数和最小公倍数问题》给出两者的取值,要求反推满足条件的正整数数对 (P, Q) 的组数。题目的突破口在于乘积恒等式 P × Q =...
【NOIP真题】1997 luogu-P2241 统计方形(数据加强版) | GESP三、四级以上可练习
NOIP 1997 普及组第一题(洛谷 P2241 数据加强版),主要考察组合计数原理、循环枚举与数学规律推导。本题既可以通过双重循环枚举矩形的长宽直观求解,也可以通过组合数学与求和公式实现 O(min(n, m)) 乃至 O(1) 的高效求解。同时本题也是经典的“防溢...
【NOIP真题】2007 奖学金 luogu-P1093 | 适用于 GESP四级 / CSP-J 练习
在实际的评奖评优与考务系统中,如何按照多元维度公平、唯一地确定排名次序?洛谷 P1093 [NOIP2007 普及组]《奖学金》提供了一个标准的现实场景:根据三门课程总分、单科语文分以及学号先后来打破平局。这道题是信奥考查结构体建模(struct)与多关键字自定义排序规...
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

