Минимальные простые делители
Для каждого пусть — его минимальный простой делитель. Для простого получаем .
Строим таблицу один раз до наибольшего значения в запросах. Каждая последующая факторизация может сразу использовать сохранённые делители вместо поиска делителей.
Изначально все элементы равны нулю. Перебираем кандидатов в порядке возрастания.
Если уже задано, то составное. Иначе простое: присваиваем , затем обходим его кратные, начиная с . Записываем только в те элементы, которые всё ещё равны нулю.
Так как простые числа обрабатываются в порядке возрастания, первое простое число, записанное в элемент, — это минимальный простой делитель соответствующего числа. Каждое составное будет достигнуто: его минимальный простой делитель удовлетворяет .
Как и в решете Эратосфена, меньшие составные кратные уже помечены. Простые числа больше всё равно получают свои собственные значения, хотя их циклы вычёркивания пропускаются.
Для оставшегося значения читаем . Делим на , пока оно делит , считаем деления и записываем .
Повторяем, пока не получим . Каждый шаг полностью удаляет одно простое число, поэтому пары получаются в порядке возрастания простых. Разложение числа пусто.
Построение таблицы занимает времени и памяти. Запись только в незаданные элементы сохраняет минимальный делитель; циклы вычёркивания при этом всё равно проходят по уже заданным элементам.
Каждое успешное деление уменьшает значение в запросе хотя бы вдвое. Поэтому разложение занимает времени. Запрос использует дополнительной памяти, не считая возвращаемых пар.
#include <bits/stdc++.h>
using namespace std;
vector<int> spf;
void build(int n) {
spf.assign(n + 1, 0);
for (int p = 2; p <= n; p++) {
if (spf[p] != 0) {
continue;
}
spf[p] = p;
if (p > n / p) {
continue;
}
for (long long x = 1LL * p * p; x <= n; x += p) {
if (spf[(int)x] == 0) {
spf[(int)x] = p;
}
}
}
}
vector<pair<int, int>> factor(int x) {
vector<pair<int, int>> res;
while (x > 1) {
int p = spf[x], e = 0;
while (x % p == 0) {
x /= p;
e++;
}
res.push_back({p, e});
}
return res;
}