Xoranna got into big trouble. The prime master locked her in his secret room and told her not to get out until he returns or else… He didn't say. "What would that or else mean?" she wonders.
Nevertheless, she wants to get out, and fast. She sees the lock from the distance, it requires one number to open. The number can be huge, since the lock fits up to 15 digits! Not discouraged, she checks further and finds a small note on the ground:
"Seek as far as you can go.
From the interval I give
Two coprimes you must retrieve.
Their difference should be the greatest
Of all coprime pairs you can test.
Know this difference and you may go."
Xoranna then notices two numbers on the back of the note. Could this be the interval in the riddle? Possibly, since the first one is the smallest. However, she doesn't have the time to test all numbers until the prime master returns, so she needs your help to open the lock.
Input
The first line contains the first number while the second line contains the second number.
Output
A natural number that solves the riddle for the given input. If the solution numbers are A and B, then the answer is B-A+1.
Constraints
- 0 < a ≤ b < 1015
- You only have one chance to open the lock!
- If there are no two such numbers, please print -1.
- Two numbers are coprime if their greatest common divisor is 1.
Sample
| Input | Output |
|---|---|
| 1 10 | 10 |
You need to answer the following question:
Find two integers in the interval [A, B] such that they are coprime and the distance between them is maximum.
Let's start with a brute force idea:
1 for(int i=a; i<=b; ++i) 2 for(int j=b; j>=a; --j) 3 if(gcd(i, j) == 1) 4 result = max(result, j-i+1);
Let's make a few observations:
- If one of the numbers is prime, there are a lot of valid options for the other (anything except multiples of said prime). Therefore, a starting point for the solution would be choosing the first prime in the interval together with the largest number that is not a multiple of it.
- Better pairs might still exist. However, we can infer a critical piece of information from the previous observation: the first number should be chosen from the interval [A, firstPrime]. That is, we only improve the previous solution.
- Since there are intervals that contain only one prime, towards the upper bound, we also consider the reverse: search in [A, firstPrime] and [lastPrime, B].
- To make sure that the search interval is not too large, we need to take a look at a prime gap table. For the values of A and B used in this problem, the largest prime gap does not exceed 1000.
1 long long gap = 1000; 2 for(long long i=a; i<=min(a+gap, b); ++i) 3 for(long long j=b; j>=max(a, b-gap); --j) 4 if(i <= j && gcd(i, j) == 1) 5 result = max(result, j-i+1);
