1388. Factorise Many Numbers Fast
For each of q values print its prime factorisation as alternating primes and
exponents, in increasing order of prime.
12 -> 2 2 3 1 because 12 = 2^2 * 3
97 -> 97 1
1000000 -> 2 6 5 6 because 10^6 = 2^6 * 5^6
Problem 1316 prints the factors with repetition for one value. This prints
exponents, for up to 10^5 values, which is what forces the technique.
## What most people try first
Trial division per query, up to the square root. Each query is up to 1000
divisions at n = 10^6, so 10^5 queries is 10^8 divisions. That is slow
enough to matter and it repeats the same work on every query.
## One table of smallest prime factors
Sieve a table spf[v] holding the smallest prime factor of every v up to
10^6, which is the same table problem 1352 builds:
spf[v] = v for all v
for i from 2 while i*i <= LIM:
if spf[i] == i: i is prime
for j from i*i step i to LIM:
if spf[j] == j: spf[j] = i only the first prime to reach j
The guard if spf[j] == j is what makes it the smallest factor rather than
the largest: a later, bigger prime must not overwrite an entry a smaller prime
already claimed.
Then each factorisation is a walk down the table:
while n > 1:
p = spf[n], e = 0
while n % p == 0: n = n / p, e = e + 1
emit p and e
## Why the walk is short, and why the primes come out sorted
Each step divides n by at least 2, so there are at most log2(10^6) = 19
iterations, and n has at most 7 distinct prime factors below 10^6, since
2*3*5*7*11*13*17 is already 510510.
The primes come out in increasing order for free: spf[n] is by definition the
smallest prime dividing n, and once every copy of it is divided out, the new
smallest prime factor is strictly larger. So no sorting step is needed and the
output order is pinned by the method rather than by a convention.
## Overflow
Nothing here overflows. Values are at most 10^6, exponents are at most 19,
and the only product formed is i * i inside the sieve, which stops at 10^6.
All are far inside a signed 32-bit integer, whose limit is 2147483647, so this
problem carries no overflow tag. The table itself is 10^6 integers, four
megabytes as 32-bit values, which is the real resource to think about.
## Cost
O(LIM log log LIM) once, then O(log n) per query.
Constraints - `1 ≤ q ≤ 100000` - `2 ≤ n ≤ 1000000` - Primes must appear in increasing order.
Input
The first line contains q.
Each of the next q lines contains one integer n.
Output
For each query print one line: the primes dividing n in increasing order, each followed by its exponent, all separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.