Метод разложения на простые множители при решении олимпиадных задач заключается в представлении составного числа в виде произведения простых чисел. 2

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

1. Найти наименьший простой делитель числа из таблицы простых чисел. 1 Если результат деления равен 1, то число простое и само является своим разложением на простые множители. 1 Если нет, то нужно перейти к следующему шагу. 1
2. Найти наименьший простой делитель числа, полученного на предыдущем шаге. 1 Для этого последовательно перебирают числа из таблицы простых чисел, начиная с наименьшего простого делителя предыдущего числа. 1
3. Продолжать процесс до тех пор, пока в частном не получится единица. 2 На последнем шаге будет искомое разложение числа на простые множители. 1

В разложении числа простые множители могут повторяться. 1 Повторяющиеся простые множители можно записать более компактно, используя степень числа. 1

Разложение на простые множители помогает, например, найти наибольший общий делитель (НОД) двух чисел. 4 Для этого нужно выписать отдельно только те множители, которые входят во все заданные числа, и перемножить их. 4 Результат перемножения и есть НОД. 4