1352. Smallest Prime Factor, Many Times
Given n and then q queries, print the smallest prime factor of each queried
value. Every query is between 2 and n.
Factorising each query separately costs O(sqrt(n)) each, which is too slow for
10^5 queries.
Modify the sieve instead. An ordinary sieve records only whether a number is prime. Record WHICH prime struck it out and you get far more for the same work:
spf[i] = i for all i
for p from 2 while p*p <= n:
if spf[p] == p: p is prime, nothing struck it yet
for m = p*p, p*p+p, ... up to n:
if spf[m] == m: only if nothing has struck m before
spf[m] = p
The inner guard is what makes it the SMALLEST prime factor: since p increases,
the first prime to reach a number is its smallest, and later ones must not
overwrite it.
Starting the inner loop at p*p rather than 2p is safe, because any smaller
multiple of p has a smaller prime factor and was already handled.
Anything left with spf[i] == i at the end is prime, its smallest prime factor
being itself. That falls out without a separate check, and it is why this table
also factorises any value completely in O(log n) steps afterwards.
Constraints - `2 ≤ n ≤ 1000000` - `1 ≤ q ≤ 100000` - `2 ≤ query ≤ n`
Input
The first line contains two integers n and q.
The second line contains q space-separated queries, each between 2 and n.
Output
Print q values separated by single spaces: the smallest prime factor of each queried value, in the order asked.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.