Факторизация
Храним ту часть числа, которая ещё не разложена. Пробуем , затем нечётных кандидатов .
Для каждого кандидата делим оставшееся значение на , пока оно делится. Если было делений, записываем .
Условие цикла проверяем для текущего остатка :
Оно равносильно , но без риска переполнения. По мере удаления множителей уменьшается, поэтому цикл может остановиться раньше.
После цикла добавляем , если . Разложение числа пусто.
Перед каждым кандидатом все меньшие простые множители уже полностью удалены.
Если бы составной кандидат делил текущий остаток, то один из его меньших простых множителей тоже делил бы этот остаток. Это противоречит инварианту. Следовательно, каждый записанный кандидат — простое число.
В момент завершения следующий кандидат удовлетворяет . Если бы остаток был составным, у него был бы простой делитель не больше . Этот делитель меньше и уже удалён — снова противоречие.
Таким образом, последний остаток — простое число, и на выходе получаются простые множители в порядке возрастания.
Для исходного числа время работы в худшем случае — ; оно достигается, когда простое. Для составных чисел удаление множителей может сильно ускорить работу.
Простых множителей с учётом кратности не больше , поэтому результат занимает памяти. Функция использует дополнительной памяти.
После удаления и каждый оставшийся простой множитель имеет вид или . Можно ограничить кандидатов числами этого вида.
Колесо обобщает эту идею: удаляем несколько маленьких простых чисел, а затем перебираем только числа, взаимно простые с их произведением. Некоторые кандидаты всё равно составные. Фиксированное колесо уменьшает константу, сохраняя оценку в худшем случае.
Если чисел много и все они не превосходят , найдём решетом все простые числа до . Пробуем только эти простые числа и останавливаемся, когда для текущего остатка.
Список должен содержать каждое простое число, которое может понадобиться до выполнения этого условия остановки. Только тогда то же доказательство гарантирует, что оставшееся значение больше — простое.
После предподсчёта каждый запрос проверяет не более кандидатов и выполняет успешных делений, где — количество простых чисел, не превосходящих .
#include <bits/stdc++.h>
using namespace std;
vector<pair<long long, int>> factor(long long n) {
vector<pair<long long, int>> res;
for (long long p = 2; p <= n / p; p += (p == 2 ? 1 : 2)) {
int e = 0;
while (n % p == 0) {
n /= p;
e++;
}
if (e > 0) {
res.push_back({p, e});
}
}
if (n > 1) {
res.push_back({n, 1});
}
return res;
}