Разложение числа на простые множители онлайн

Разложение числа на простые множители − теория, алгоритм, примеры и решения

Один из простейших способов разложить число на простые множители − это проверить, делится ли данное число на 2, 3, 5 ,... и т.д., т.е. проверить, делится ли число на ряд простых чисел. Если число n не делится ни на какое простое число до , то даннаое число является простым, т.к. если число составное, то имеет по крайней мере два множителя и оба они не могут быть больше .

Представим алгоритм разложения числа n на простые множители. Подготовим заранее таблицу простых чисел до s=. Обозначим ряд простых чисел через p₁, p₂, p₃, ...

Алгоритм разложения числа на простые делители:

1. Исходный данные n, i=0, s=.
2. Увеличить i: i=i+1.
3. Если p_i>s, то сохранить значение n и перейти к шагу 8.
4. n делить на p_i.
5. Если n делится на p_i, то сохранить значение p_i. Вычислить k=n/p_i. Брать в качестве n число k: n=k.
6. Если n не делится на p_i, то перейти к шагу 2.
7. Если n≠1, перейти к шагу 4.
8. Остановить процедуру.

Пример 1. Разложить число 153 на простые множители.

Решение. Нам достаточно иметь таблицу простых чисел до , т.е. 2, 3, 5, 7, 11.

Делим 153 на 2. 153 не делится на 2 без остатка. Далее делим 153 на следующий элемент таблицы простых чисел, т.е. на 3. 153:3=51. Заполняем таблицу:

Теперь проверяем, делится ли число 51 на 3. 51:3=17. Заполняем таблицу:

Далее проверяем, делится ли число 17 на 3. Число 17 не делится на 3. Оно не делится и на числа 5, 7, 11. Следующий делитель больше . Следовательно 17 простое число, которое делится только на себя: 17:17=1. Процедура остановлена. заполняем таблицу:

Выбираем те делители, на которых числа 153, 51, 17 делились без остатка, т.е. все числа с правой стороны таблицы. Это делители 3, 3, 17. Теперь число 153 можно представить в виде произведения простых чисел: 153=3·3·17.

Пример 2. Разложить число 137 на простые множители.

Решение. Вычисляем . Значит нам нужно проверить делимость числа 137 на простые числа до 11: 2,3,5,7,11. Поочередно делив число 137 на эти числа выясняем, что число 137 не делится ни на одно из чисел 2,3,5,7,11. Следовательно 137 простое число.