Найдите минимальную сумму пары, НОД которой больше 1

Даны два положительных целых числа A и B. Задача состоит в том, чтобы найти два положительных целых числа, принадлежащих интервалу [A, B], таких, что их НОД больше 1, а их сумма является минимальной среди всех возможных пар.

Input: 2, 3
Output: -1
Explanation: Clearly there doesn’t exits any pair for which gcd is greater than 1, Hence we simply return -1.

Input: 2 10
Output: 2 4
Explanation: The smallest pair for which GCD is greater than 1 is 2, 4 .

Подход: Проблема может быть основана на следующем наблюдении:

Two consecutive even numbers have GCD greater than 1 and the difference among them is also minimum.

Основываясь на приведенном выше наблюдении, оптимально найти пару из двух последовательных четных чисел, значения которых находятся ближе всего к нижней границе диапазона. Следуйте шагу ниже, чтобы решить эту проблему:

• Проверить абсолютную разницу заданного диапазона abs(A – B)
  • Если abs(A – B) <= 1 , то не существует пары, у которой gcd больше 1, выведите -1 .
• Если первое значение четное
  • выведите (A, A+2) , потому что это наименьшие числа, у которых НОД больше 1.
• Если первое значение нечетное
  • Проверьте, если (B – A) == 2 , тогда выведите -1 , потому что НОД двух последовательных нечетных чисел всегда равен 1.
  • Проверьте, если (B – A) > 2 , то
    • Если A делится на 3, то выведите (A, A+3) ,
    • В противном случае выведите (A+1, A +3) .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(1)
Вспомогательное пространство: O(1)