If we precompute the primacity of each number, then answering test cases just takes a sweep over the precomputed results.

To compute the primacity, one option is to use a modified Sieve of Eratosthenes. In the normal sieve, we iterate upwards and whenever we find a prime number, we cross off all multiples of it from our list of primes. Rather than crossing off a multiple, we can add ~1~ to a counter that keeps track of its primacity.

For example, ~2~ is prime, so we add ~1~ to the primacity of ~4~, ~6~, ~8~, ~10~, etc. ~3~ is the next prime, so we add ~1~ to the primacity of ~3~, ~6~, ~9~, ~12~, etc.

The time complexity is the same as the standard sieve, ~\mathcal O(N \log \log N)~ for the integers ~1~ to ~N~.