Подсчитайте числа до N, у которых НОД с N меньше этого числа

Учитывая целое число N , задача состоит в том, чтобы подсчитать значения K ( где 1 ≤ K≤ N ), такие, что 1< GCD (K, N) < K .

Примеры:

Input: N = 10
Output: 3
Explanation: The values of K which satisfies the given conditions are: 

• K = 4, gcd(4, 10) = 2
• K = 6, gcd(6, 10) = 2
• K = 8, gcd(8, 10) = 2

Input: N = 15
Output: 4
Explanation: The values of K which satisfies the given conditions are: 

• K = 6, gcd(6, 15) = 3
• K = 9, gcd(9, 15) = 3
• K = 10, gcd(10, 15) = 5
• K = 12, gcd(12, 15) = 3

Наивный подход: самый простой подход — перебрать диапазон [1, N] и проверить для каждого числа, удовлетворяет ли оно заданному условию или нет. Наконец, выведите количество таких чисел.

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

Эффективный подход: идея состоит в том, чтобы найти все числа в диапазоне [1, N] , для которых gcd(K, N) = 1 и gcd(K, N) = K, а затем, наконец, удалить все эти числа из N , чтобы получить окончательный ответ. Выполните следующие шаги, чтобы решить проблему:

• Сохраните все простые множители N , используя Решето Эратосфена.
• Храните количество всех чисел в диапазоне [1, N], для которого gcd(N, K) = K в переменной count1 .
• Храните количество всех чисел в диапазоне [1, N], для которого gcd(N, K) = 1, используя Тотиентная функция Эйлера в переменной count2 .
• Удалите эти числа из N , обновив ans до N – (count1 + count2) .
• Выведите значение ans в качестве результата.

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

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