Loading...
Loading...
Loading...
A coding-contest helper answers many prime questions, so it builds a prime table once, when the class is first used, and answers each question instantly.
Write a class PrimeTable with static final int LIMIT = 1000000, static final arrays filled in a static block (a sieve of all numbers up to LIMIT, the list of primes, and a running count), and static methods isPrime(int n), nth(int k) and countBetween(int a, int b).
prime x, nth k or count a b.prime: x PRIME or x NOT PRIME. nth: the k-th prime. count: the number of primes from a to b, both included.Example
Input
4 prime 97 nth 5 count 1 10 count 14 16
Output
97 PRIME 11 4 0
The 5th prime is 11; there are 4 primes up to 10 and none from 14 to 16.
Try the problem first. Open one hint at a time.
A static block runs once, before the first use of the class, which is the right place for slow set-up work.
Sieve: for each i from 2 with i * i <= LIMIT that is still unmarked, mark i*i, i*i + i, … as not prime.
countUpTo[i] = number of primes ≤ i; then a range count is countUpTo[b] - countUpTo[a - 1].
A static final array can be assigned once inside the static block; its contents can still be filled.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor