Problem: numtheory2
After intense lobbying by prime number enthusiasts, Jeopardy has decided to include some trivia on prime numbers very soon. Their first category will be on "Closest/Furthest Primes," and they need your help with it.
You need to answer queries of the following format: given two numbers L and U, find the two adjacent primes p1, p2 between L and U, inclusive, (L ≤ p1 < p2 ≤ U) that are either closest or farthest away. (Two primes are called adjacent if there are no other primes in between.) If multiple pairs of adjacent primes give the same minimum/maximum distance, you must output the first pair of such primes.
Input
The input consists of multiple test cases, each on its own line. Each line will be of the format:
The first pair of adjacent primes between L and U with minimum/maximum distance.
where L < U are two 32-bit signed integers. It is guaranteed that 1 ≤ U – L ≤ 1,000,000.
Input will be terminated by EOF.
Output
For each test case, output should be the in the format (on its own line):
What are p1 and p2?
where p1, p2 are the first pair of adjacent primes between L and U that have the minimum or maximum distance (as specified in the test case).
If no pair of adjacent primes between L and U exists, output:
That's a very good answer, thank you for responding.
Sample Input
The first pair of adjacent primes between 2 and 4 with minimum distance. The first pair of adjacent primes between 1 and 1000000 with maximum distance. The first pair of adjacent primes between 14 and 18 with minimum distance.
Sample Output
What are 2 and 3? What are 492113 and 492227? That's a very good answer, thank you for responding.