一道+ / edao.plus

质因数分解

每个合数都能唯一写成质数的乘积；求约数个数、公约数、最小公倍数的底层语言。

直观场景

质因数像一个数的“基因”。两个数比较约数、倍数关系，不看它们的十进制长相，只看基因组成。

推导思路

  1. 任何 > 1 的整数 = 质数的乘积，且分解方式唯一（算术基本定理）。
  2. 约数个数：若 n = p₁^a₁ · p₂^a₂ · … · pₖ^aₖ，则约数个数 = (a₁+1)(a₂+1)…(aₖ+1)。
  3. 最大公约数：每个质因数取最小指数相乘。
  4. 最小公倍数：每个质因数取最大指数相乘。

公式 / 要点

  • 分解：试除法，从最小质数 2 开始除。
  • GCD × LCM = a × b（两数之积）。

典型例题

1约数个数
360 有多少个正约数？
  1. 360 = 2³ × 3² × 5。
  2. 约数个数 = (3+1)(2+1)(1+1) = 24。
2GCD 与 LCM
求 gcd(84, 90) 与 lcm(84, 90)。
  1. 84 = 2² · 3 · 7；90 = 2 · 3² · 5。
  2. GCD：2¹ · 3¹ = 6。
  3. LCM：2² · 3² · 5 · 7 = 1260。
  4. 验证：6 × 1260 = 7560 = 84 × 90。

常见误区

  • 判断质数时要到 √n 就够了。
  • 写分解时按升序排质因数，便于比较。

用到“质因数分解”的题目

#10042 质因数分解·乘积问题
数论四年级
#10163 因数个数·最小值
数论六年级
#10187 质因数分解·复杂乘积
数论六年级
#10188 最大公约数·多数分组
数论六年级
#10192 因数个数·构造问题
数论六年级

相关知识点

整除特征