Для того что понять как раскладывать число на простые множители, вспомним а что такое простые множители? Итак, каждый простой множители — это простое число. В произведении 2 · 5 · 7 — 3 простых множителя: 2, 5 и 7.
Разложение на простые множители — это представление числа в виде простых множителей. К примеру, число 20 можно представить в виде произведения 2 · 2 · 5. Все числа больше единицы можно разложить на множители, за исключением простых чисел, т.к. простое число делится на само себя и на единицу.
Как разложить число на простые множители?
В общем случае алгоритм разложения числа выглядит так:
- Найти наименьший простой делитель для искомого числа, путем перебора простых чисел, т.е. то число на которое делится искомое без остатка и оно является простым делителем;
- Если частное равно единице — прекращаем деление и записываем полученный результат;
- Если частное больше единицы, находим наименьший простой делитель для полученного частного, аналогичным образом (путем перебора простых чисел);
- Повторяем пункты 2-3.
Примеры
Пример 1: разложить число 20 на простые множители
1. Простые числа на которые можно разделить 20 — 2 и 5. Наименьшее из них 2. Делим 20 на 2 = 10.
2. Простые числа на которые можно разделить 10 — также 2 и 5. Наименьшее из них 2. Делим 10 на 2 = 5.
3. Простые числа на которые можно разделить 5 — только 5. Делим 5 на 5 = 1.
Ответом будет последовательность простых множителей 2 · 2 · 5.
Для удобства можно записывать вычисления в таком виде:
20 = 2 · 2 · 5;
| 20 | 2 |
| 10 | 2 |
| 5 | 5 |
| 1 |