In this problem, we asked to find the closest, as well as the most distant, pairs of
adjacent primes
within a specified range. This range is given by two integers,
L and
U, where
1 <= L < U <= 2,147,483,647. You should recognize this upper bound as the maximum
positive value that can fit inside a
signed 32-bit integer (i.e. (2^31)-1, or
INT_MAX in
C++).
Let's take a quick review of some definitions. A number is a
prime, if and only if it is a natural
number greater than 1 and has no positive divisors other than 1 and itself.
Adjacent primes, as
described in the problem statement, are two numbers that are both primes, but there are no other prime numbers
between the adjacent primes. Note this does not mean they are necessarily adjacent in the sequence of natural
numbers, rather, any two consecutive primes in a sorted list of all primes will be adjacent primes.
We are asked for the closest and most distant adjacent prime pairs within a given range. We know the bounds of
this range, and that its width will never exceed 1,000,000. Since the time limit for this problem is 3 seconds,
and we are not given a maximum number of test cases to process, it should be clear that we will need to
formulate a solution that reuses some of the work to determine the primes.
So how should we compute the prime numbers contained by the given range?
Sieve of Eratosthenes
A common algorithm to determine all prime numbers between range [0..N] is the
Sieve of Eratosthenes. This algorithm is a
major improvement upon the naive approach, which typically involves a for-loop up to N and testing every
possible divisor with the modulus operator. Basic usage of the sieve algorithm involves a boolean array of size
N+1, with all elements initialized to
true (except for 0 and 1, which are set to
false). Then, a for-loop iteratively scans each index of the array, starting from i = 2, and if the
element at index i is true (i.e. prime), an inner for-loop marks all multiples of i as
false. Once
the outer loop completes, the indices of all elements that are
true represent the prime numbers up
to N.
This basic implementation typically looks something like this:
We can make several improvements to this algorithm. One significant improvement involves realizing that we only
need to check divisors up to
sqrt(N), changing the growth rate from
O(N) to
O(sqrt(N)). Also, there is no need to test divisors for even numbers, since the only even prime
is 2. After making the adjustments, our code now looks like the following:
Optimized Prime Testing
In order to be fast enough for large ranges, we can extend our algorithm such that
optimized prime
testing is used to determine primality for large numbers. Essentially, we will run the sieve with an
upper bound of
sqrt(INT_MAX) before processing any test cases and store the primes in a
std::vector<int> as part of the sieve algorithm. When we want to determine the primality of a
number larger than
sqrt(N) (as above), we'll determine if
N is divisible by any prime
divisors
<= sqrt(N), which are stored in our
std::vector<int>. If the large
number being tested for primality is divisible by any of the smaller primes, it is not a prime number.
All we need to do is modify our sieve function to add primes to a
std::vector<int> as they
are discovered, and write a helper function to handle optimized prime testing.
Finishing our implementation
All that's left to do now is write rest of
int main to read input, iterate over the range specified
by each test case and use our
isPrime helper to perform the primality test, store the primes being
considered, find the closest and most distant adjacent primes, and output the result.
Links
C++ References