См. также:
Разложение числа на простые множители
Натуральное число n называется делителем целого числа m, если для подходящего целого числа k верно равенство m = n ∙ k. В этом случае говорят, что m делится на n или что число m кратно числу n.
Простым числом называют натуральное число p ≥ 2, делящееся только на себя и на единицу. Составным числом называют число, имеющее больше двух различных делителей (любое целое число m, не равное 0 и 1, имеет как минимум два делителя: 1 и |m|; делителями нуля являются все натуральные числа). Например, числа 2, 3, 5, 7, 11 – простые, а числа 9 = 3∙3, 26 = 2∙13 – составные.
Любое натуральное число n, большее единицы, можно разложить в произведение простых чисел, причём это разложение единственно с точностью до порядка следования сомножителей.
Данная программа раскладывает заданное число в произведение простых множителей
Как разложить число на множители?
В школе на уроках математики разложение числа на множители обычно записывают столбиком (в две колонки). Делается это так: в левую колонку выписываем исходное число, затем
- Берём самое маленькое простое число — 2 и по признакам делимости или обычным делением проверяем, делится ли наше число на 2.
- Если делится, то в правую колонку выписываем 2. Далее делим исходное число на 2 и записываем результат в левую колонку под исходным числом.
- Если не делится, то берём следующее простое число — 3.
Повторяем эти шаги, при этом работаем уже с последним числом в левой колонке и с текущим простым числом. Разложение заканчивается, когда в левой колонке будет записано число 1.
Чтобы лучше это понять, разберём несколько примеров.
Пример. Разложить на множители число 84.
Решение.
Записываем число 84 в левую колонку:
Берём первое простое число - два и проверяем, делится ли 84 на 2. Так как 84 оканчивается на 4, а 4 делится на 2, то и 84 делится на 2 по признаку делимости. Записываем 2 в правую колонку. 84:2 = 42, число 42 записываем в левую колонку. Получили вот что:
Теперь работаем уже с числом 42. Число 42 делится на 2, поэтому записываем 2 в правую колонку, 42:2 = 21, число 21 записываем в левую колонку.
Число 21 на 2 не делится, поэтому проверяем его делимость на следующее простое число — 3. Число 21 делится на 3, 21:3 = 7. Записали 3 в правую колонку, 7 - в левую. Получили
Число 7 - простое число, поэтому в правой колонке записываем 7, в левую пишем 1. В итоге получили:
Всё, число разложено!
В результате в правой колонке оказались записаны все простые множители числа 84. То есть 84=2∙2∙3∙7.