You need to answer the following question:

Find two integers in the intervalsuch that they are coprime and the distance between them is maximum.[A, B]

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
. That is, we only improve the previous solution.`[A, firstPrime]` - Since there are intervals that contain only one prime, towards the upper bound, we also consider the reverse: search in
and`[A, firstPrime]`.`[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
and`A`used in this problem, the largest prime gap does not exceed`B`.`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);