Задача: записать все делители числа 84.
Простое разложение 84 84 = 2^2 · 3 · 7
Правило для делителей Логично: любой делитель числа 84 имеет вид 2^a · 3^b · 7^c, где a ∈ {0,1,2}, b ∈ {0,1}, c ∈ {0,1}.
Перечисление всех делителей
- При a = 0:
- b = 0, c = 0 → 1
- b = 1, c = 0 → 3
- b = 0, c = 1 → 7
- b = 1, c = 1 → 21
- При a = 1:
- b = 0, c = 0 → 2
- b = 1, c = 0 → 6
- b = 0, c = 1 → 14
- b = 1, c = 1 → 42
- При a = 2:
- b = 0, c = 0 → 4
- b = 1, c = 0 → 12
- b = 0, c = 1 → 28
- b = 1, c = 1 → 84
- Итоговый список делителей (упорядочив по возрастанию) 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84
Дополнительная проверка: делители можно получить и парами, умножающимися друг на друга на 84: (1, 84), (2, 42), (3, 28), (4, 21), (6, 14), (7, 12). Всего 6 пар, значит 12 делителей, что совпадает с вычислением.