Количество чисел между L и R, взаимно простых с P

Найдите количество чисел между L и R, взаимно простых с P.

Примечание: Два числа X и Y взаимно просты друг с другом, если их НОД равен 1.

Примеры :

Input: L = 1, R = 10, P = 16
Output: 5
Explanation: The numbers coprime with P are 1, 3, 5, 7, 9

Input: L = 10, R = 20, P = 15
Output: 6

Подход : проблема может быть решена с помощью простой математической концепции.

Traverse from i = L to R and check if the GCD between i and P is 1 or not.

Выполните следующие шаги, чтобы решить проблему:

• Инициализировать количество = 0.
• Пройдитесь по диапазону и проверьте, взаимно ли это число с P.
  • Для проверки взаимно простого проверьте, равен ли НОД двух чисел 1 или нет, если да, то иначе нет.
  • Если да, добавьте 1 к счету.
• После обхода диапазона вернуть счет.

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

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