1383. Is Each Of Them Prime
For each of q values print yes if it is prime and no otherwise.
2 -> yes
9 -> no
97 -> yes
1 -> no 1 is not prime
## What most people try first
Trial division of each value by every integer from 2 up to its square root.
That is correct, and at n = 10^12 the square root is 10^6, so with 500
queries it is 5 * 10^8 divisions. A division is one of the slowest integer
operations there is, so this is the rare case where the constant factor decides
whether the solution passes.
## Why the square root is enough
If n = u * v with both factors above sqrt(n), then u * v > n, which is a
contradiction. So any composite n has a factor at or below sqrt(n), and the
smallest such factor is necessarily prime, since any factor of it would be a
smaller factor of n.
## Why a sieve to 10^12 is not an option
The obvious speed-up is a sieve of Eratosthenes up to 10^12. One byte per
value is 10^12 bytes, a terabyte. Even one bit per value is 125 gigabytes.
The array cannot be allocated, so the sieve has to be used on a range it can
actually cover.
## Sieve the small primes once, then divide only by those
The useful observation is that only the prime divisors matter, and they are
all at most 10^6. So:
sieve once up to 1100000 78498 primes below 10^6
for each query: divide n by each prime while prime*prime <= n
There are 78498 primes below 10^6 against 10^6 integers, so this is about
13 times less work: roughly 4 * 10^7 divisions in total, which is fast.
The sieve itself is 10^6 bytes and takes a few milliseconds.
The limit is 1100000 rather than exactly 10^6 so there is margin above
sqrt(10^12) and the loop condition never runs past the end of the table.
## Overflow
n reaches 10^12, which does not fit in a signed 32-bit integer at all,
since INT_MAX is 2147483647. A 32-bit build answers no for the prime
999999000001 because the truncated value is composite. The comparison
p * p <= n with p up to 1.1 * 10^6 reaches 1.21 * 10^12, so it too
needs 64 bits. In JavaScript these stay below 2^53, so a plain Number is
exact here, provided no bitwise operator is used.
## Cost
O(sqrt(N) / log(sqrt(N))) divisions per query after an O(S log log S)
sieve.
Constraints - `1 ≤ q ≤ 500` - `1 ≤ n ≤ 1000000000000` - `1` is not prime.
Input
The first line contains q.
Each of the next q lines contains one integer n.
Output
For each value print yes if it is prime and no otherwise, one per line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.