Гадание - 2
(Время: 1 сек. Память: 16 Мб Сложность: 20%)
Маша недавно прочитала в книге «Теория чисел и предсказание будущего» о новом способе гадания. Способ заключается в следующем: надо выбрать целое положительное число N и посчитать количество чисел, меньших N и взаимно простых с ним. Это количество и будет результатом гадания.
Поскольку гадать приходится достаточно часто, а процесс гадания достаточно трудоемок, Маша попросила вас написать программу, считающую результат гадания.
Два числа называются взаимно простыми, если их наибольший общий делитель равен 1. Наибольшим общим делителем двух чисел a и b называется наибольшее целое положительное число, на которое делятся и a, и b.
Входные данные
Входной файл INPUT.TXT содержит целое положительное число N (1 ≤ N ≤ 105).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно число – результат гадания.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 13 | 12 |
| 2 | 6 | 2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
