Factorization
Maintain the part of the number that has not yet been factored. Try , then the odd candidates .
For each candidate , divide the remaining value by while it is divisible. If there were divisions, record .
Check the loop condition against the current remainder :
This is equivalent to without risking overflow. As factors are removed, decreases, so the loop may stop earlier.
After the loop, append if . The factorization of is empty.
Before each candidate, all smaller prime factors have been completely removed.
If a composite candidate divided the current remainder, one of its smaller prime factors would divide that remainder too. This contradicts the invariant. Therefore, every recorded candidate is prime.
At termination, the next candidate satisfies . If the remainder were composite, it would have a prime divisor at most . That divisor is smaller than and has already been removed, again a contradiction.
Thus the final remainder is prime, and the output contains prime factors in increasing order.
For an original input , the worst-case time is , reached when is prime. Removing factors can make composite inputs much faster.
There are at most prime factors counted with multiplicity, so the output uses space. The function uses additional memory.
After removing and , every remaining prime factor has the form or . We can restrict the candidates to these forms.
A wheel generalizes this idea: remove a few small primes, then visit only numbers coprime to their product. Some candidates are still composite. A fixed wheel reduces constant factors while keeping the worst-case bound.
For many inputs bounded by , sieve all primes through . Try only these primes, stopping when for the current remainder.
The list must cover every prime that could be needed before this stopping condition is reached. Only then does the same proof guarantee that a leftover value greater than is prime.
After preprocessing, each query tests at most candidates and performs successful divisions, where is the number of primes at most .
#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;
}