Solution of 50 Shades of Prime

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