数论知识-----质因数分解（竞赛必会）
🌟 第一章：什么是质因数分解？
1、🧠故事：拆积木游戏 🧱
一个大数字就像一个“大积木”：
👉 我们要把它拆成最小的“质数积木”
2、🎯什么是质数？
👉 只能被：
1 和 自己整除的数
例如：
2, 3, 5, 7, 11 ...3、🌰例子：拆 12
12 = 2 × 2 × 3👉 这就是质因数分解！
🌟 第二章：为什么重要？
🎯竞赛中常见用途：
| 场景 | 用途 |
|---|---|
| 判断终止小数 | 只含2和5 |
| 求约数个数 | 用指数计算 |
| 最大公约数 | 分解后取最小指数 |
| 最小公倍数 | 分解后取最大指数 |
🌟 第三章：最基础算法（试除法）
1、🧠故事：试钥匙开锁 🔑
你拿一把锁（数字 n）
用钥匙（2,3,4,5…）一个个试
2、🎯核心代码（必背🔥）
#include <iostream> using namespace std; void factor(int n){ for(int i = 2; i * i <= n; i++){ while(n % i == 0){ cout << i << " "; n /= i; } } if(n > 1) cout << n; } int main(){ int n; cin >> n; factor(n); }3、🌰例子：
输入：
n = 60输出：
2 2 3 5🌟 第四章：为什么只要到 √n？
1、🧠故事：找因子配对
36 = 2×18 = 3×12 = 4×9 = 6×6👉 小的因子找完，大的就自动出现！
2、🎯结论：
只需要枚举到 sqrt(n)🌟 第五章：进阶版（统计指数）
1、🎯目标：
把：
60 = 2² × 3¹ × 5¹2、✨代码：
void factor(int n){ for(int i = 2; i * i <= n; i++){ if(n % i == 0){ int cnt = 0; while(n % i == 0){ n /= i; cnt++; } cout << i << "^" << cnt << endl; } } if(n > 1) cout << n << "^1"; }🌟 第六章：经典题型1（终止小数）
1、🎯判断：
1/n 是否终止2、✨规则：
👉 只含：
2 和 53、✨代码：
bool isFinite(int n){ while(n % 2 == 0) n /= 2; while(n % 5 == 0) n /= 5; return n == 1; }🌟 第七章：经典题型2（约数个数）
1、🎯公式：
如果：
n = p1^a × p2^b × p3^c👉 约数个数：
(a+1)(b+1)(c+1)2、🌰例子：
12 = 2² × 3¹👉 个数：
(2+1)(1+1) = 6🌟 第八章：经典题型3（最大公约数）
1、🎯方法：
分解后取最小指数
2、🌰例子：
12 = 2² × 3¹ 18 = 2¹ × 3²👉 gcd：
2¹ × 3¹ = 6🌟 第九章：经典题型4（最小公倍数）
👉 取最大指数！
🌰例子：
lcm = 2² × 3² = 36🌟 第十章：竞赛技巧总结🔥
🎯必背结论：
1️⃣ 分解模板
for(int i=2;i*i<=n;i++)2️⃣ 最后判断
if(n > 1)3️⃣ 常见用途
判断终止小数
约数个数
gcd / lcm
🌟 第十一章：课堂练习题
🎯练习1
分解：
84👉 答案：
2² × 3 × 7🎯练习2
判断：
1/40 是否终止？👉 ✔️ 是（只有2和5）
🎯练习3
求约数个数：
36 = 2² × 3²👉：
(2+1)(2+1)=9🎉 最终总结：
👉质因数分解 = 把数拆成质数乘积
课后习题：🌟 第1题——拆糖果 🍬
1、🎯题目
输入一个整数 n，输出它的质因数分解。
2、🌰输入
303、✅输出
2 3 54、🧠思路
👉 用“试除法”不断除
5、💻代码
for(int i=2;i*i<=n;i++){ while(n%i==0){ cout<<i<<" "; n/=i; } } if(n>1) cout<<n;🌟 第2题 ——统计指数 📊
1、🎯题目
输出形如：
2^2 3^1 5^12、🧠思路
👉 每个质因数记录次数
3、💻代码
for(int i=2;i*i<=n;i++){ if(n%i==0){ int cnt=0; while(n%i==0){ n/=i; cnt++; } cout<<i<<"^"<<cnt<<" "; } } if(n>1) cout<<n<<"^1";🌟 第3题 ——判断质数 🔍
1、🎯题目
判断 n 是否是质数
2、🧠思路
👉 没有任何因子（2~√n）
3、💻代码
bool isPrime(int n){ if(n<2) return false; for(int i=2;i*i<=n;i++){ if(n%i==0) return false; } return true; }🌟 第4题 ——约数个数 📦
1、🎯题目
求 n 的约数个数
2、🧠思路
👉 分解 → 指数+1 相乘
3、🌰例子
12 = 2² × 3¹👉 个数：
(2+1)(1+1)=64、💻代码
int ans=1; for(int i=2;i*i<=n;i++){ if(n%i==0){ int cnt=0; while(n%i==0){ n/=i; cnt++; } ans *= (cnt+1); } } if(n>1) ans*=2;🌟 第5题 ——约数和 💰
1、🎯题目
求所有约数的和
2、🧠公式
如果：
n = p^a👉 贡献：
1 + p + p² + … + p^a3、💻代码核心
int sum=1; for(int i=2;i*i<=n;i++){ if(n%i==0){ int term=1, p=1; while(n%i==0){ n/=i; p*=i; term+=p; } sum*=term; } } if(n>1) sum*=(1+n);🌟 第6题 ——最大公约数 ⚔️
1、🎯题目
用分解思想求 gcd
2、🧠思路
👉 公共质因数，取最小指数
3、🌰例子
12 = 2² × 3¹ 18 = 2¹ × 3²👉 gcd：
2¹ × 3¹ = 64、💻代码
#include <iostream> using namespace std; int gcd(int a, int b){ while(b != 0){ int t = a % b; a = b; b = t; } return a; } int main(){ int a, b; cin >> a >> b; cout << gcd(a, b) << endl; }🌟 第7题 ——最小公倍数 🧩
1、🎯题目
👉 求最小公倍数！
2、💻 公式
lcm = a / gcd(a,b) * b;3、💻代码
#include <iostream> using namespace std; int gcd(int a, int b){ while(b != 0){ int t = a % b; a = b; b = t; } return a; } int lcm(int a, int b){ return a / gcd(a, b) * b; } int main(){ int a, b; cin >> a >> b; cout << lcm(a, b) << endl; }🌟 第8题 ——是否终止小数 💧
1、🎯题目
判断：
1/n 是否终止2、🧠关键：
👉 只含 2 和 5！
3、💻代码
while(n%2==0) n/=2; while(n%5==0) n/=5; if(n==1) cout<<"YES"; else cout<<"NO";🌟 第9题 ——分解多个数 ⚙️
1、🎯题目
输入多个 n，分别分解
2、🧠技巧
👉 每个数独立处理
👉 可以用函数！
3、💻模板
void solve(int n){ for(int i=2;i*i<=n;i++){ while(n%i==0){ cout<<i<<" "; n/=i; } } if(n>1) cout<<n; }🌟 第10题 ——区间质因数统计
1、🎯题目
统计 1~n 中所有数的质因数个数总和
2、🧠思路
👉 用类似“筛法”思想
3、💻代码
int cnt=0; for(int i=2;i<=n;i++){ int x=i; for(int j=2;j*j<=x;j++){ while(x%j==0){ cnt++; x/=j; } } if(x>1) cnt++; }🎯 总结（竞赛核心）
🧠一看到题就要想到：
👉 是否能：
分解质因数？
用指数？
转换成乘法？
💎三大万能套路：
1️⃣ i*i <= n 2️⃣ while(n % i == 0) 3️⃣ if(n > 1)