Каноническое разложение на простые множители
Любое натуральное число единственным образом представляется в виде произведения простых чисел:
n = p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ
Например:
- 12 = 2² × 3
- 60 = 2² × 3 × 5
- 1000 = 2³ × 5³
Это разложение — ключ к решению большинства задач на делители.
Формула количества делителей
Если число n имеет разложение p₁^a₁ × p₂^a₂ × ... × pₖ^aₖ, то количество его делителей равно:
τ(n) = (a₁ + 1) × (a₂ + 1) × ... × (aₖ + 1)
Например:
- τ(12) = τ(2² × 3) = (2+1)(1+1) = 6
- τ(p⁴) = (4+1) = 5
Нетривиальные делители
Нетривиальные делители — это все делители числа, кроме единицы и самого числа. Если всего делителей τ(n), то нетривиальных будет τ(n) − 2.