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);