Задачі
Теорія чисел
Теорія чисел
Для заданого натурального числа n знайдіть кількість таких чисел m, що 1 ≤ m ≤ n, НСД(m, n) ≠ 1 та НСД(m, n) ≠ m. Через НСД тут позначено "Найбільший Спільний Дільник".
Вхідні дані
Кожний рядок містить одне натуральне число n (0 < n < 231
).
Вихідні дані
Для кожного значення n вивести в окремому рядку кількість шуканих чисел m.
Вхідні дані #1
1 6 10 2147000000
Вихідні дані #1
0 1 3 1340599805