质因数分解与因数
将 N 分解为质数幂并统计因数数量
质因数分解与因数 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
拆解 N
每个大于 1 的整数都能唯一表示为若干质数的乘积。找出这种分解，也就是它的质因数分解，可以解决许多数论问题。🧩
试除法思想
找出能够整除 n 的最小质数，将它除去，然后重复此过程。这种简单的试除法会逐步将 n 分解到 1。
循环到平方根
只要 i*i 不超过 n，就测试因数 i。超过平方根后，最多只可能剩下一个质因数。
while i * i <= n:
...提取每个因数
只要 i 能整除 n，就不断进行除法并记录 i。这样可以在继续处理之前，完整记录该质数的幂次。
while n % i == 0:
factors.append(i)
n //= i剩余的质因数
循环结束后，如果 n 仍大于 1，那么它本身就是一个大于平方根的质数因数。将它添加一次。
if n > 1:
factors.append(n)完整流程
这样就能在 O(sqrt n) 时间内完成质因数分解，并按顺序返回每个质数及其完整的重复次数。
def factorize(n):
f, i = [], 2
while i * i <= n:
while n % i == 0:
f.append(i); n //= i
i += 1
if n > 1: f.append(n)
return f按幂次分组
统计因数数量时，需要记录每个质数及其指数
from collections import Counter
exp = Counter(factorize(n))因数数量公式
如果 n 等于 p1^a 乘以 p2^b，那么因数数量就是 (a+1) 乘以 (b+1)。每个指数都多出一种选择。
计算因数个数
将所有质数的指数分别加 1，再把这些结果相乘。这样无需逐个列出因数，就能得到因数的总数量。
count = 1
for e in exp.values():
count *= (e + 1)因数之和
还有一个相关公式，利用每个质数的等比级数来计算因数之和。掌握它有助于解决完全数和真因数和问题。
用筛法加速
需要进行大量分解时，可以用筛法预先计算每个数的最小质因数。之后，每次查询都能在 log n 步内完成质因数分解。
快速检查
将因数个数公式应用到一个具体的数上。
回顾
现在您可以用试除法在O(sqrt n)内分解 N，处理剩余的质数，归并指数，并用乘积公式计算因数个数。✅
常见问题解答
「质因数分解与因数」课时是免费的吗？
是的 — 「质因数分解与因数」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「质因数分解与因数」这节课中我会学到什么？
将 N 分解为质数幂并统计因数数量 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「质因数分解与因数」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。