Доброго времени суток, товарищи! Сегодня мы коснемся такой темы, как факторизация числа - разложение числа на простые множители. Существование и единственность такого разложения следует из основной теоремы арифметики.
Сегодня мы поверхностно пройдемся по теме, разберем простейшим алгоритм, достаточный для олимпиад, а в следующих статьях углубимся в тему и посмотрим алгоритмы Полларда, Бента, Монте-Карло и Ферма.
Как мы знаем из предыдущих статей - делители числа будут только лишь до корня из этого числа (делители ходят парами). Значит нам достаточно перебрать все числа до корня из числа. Но почему они все будут простыми? Тут идея такая же как и у Решета Эратосфена. Если мы поделим какое-то числа на 2, столько раз, сколько оно делится на 2, то мы в дальнейшем никак не сможем поделить его на 4, 6, 8, 10, потому что на 2 число точно делиться не будет (без остатка). Следующее число так же как и у решета будет точно не составным (подробнее об этом в статье про Решето), то есть простым. Мы проверим 3, и уже точно будем знать, что число не делиться на 3 и так далее до корня из числа...
Стоить добавить, что мы обязательно уменьшаем n в процессе, чтобы проверенные делители в числе не образовывали новые, составные делители. И в конце нам обязательно нужно проверить является ли оставшееся число больше 1, ведь последний, самый большой делитель может оказаться тоже простым числом.