e-olymp 339. Опять несократимые

Задача

Дробь $\frac{m}{n}\ $ называется правильной несократимой, если [latex] 0 <  m < n [/latex] и [latex] НОД (m, n) = 1.[/latex] Найдите количество правильных несократимых дробей со знаменателем $n$.

Входные данные

Каждая строка является отдельным тестом и содержит число $n$ ([latex]n < 10^9 [/latex]). Последняя строка содержит $0$ и не обрабатывается. Количество тестов не больше $100.$

Выходные данные

Для каждого $n$ в отдельной строке вывести ответ на поставленную задачу.

Тесты

Вход Выход
12
123456
7654321
0
4
41088
7251444
552
99693
34
991
8863
0
176
56160
16
990
8862
1
5754
99291
7752
3321
0
1
1632
63272
2304
2160
99291
581293
3215788
1224262
68291
692110
0
63272
581292
1422720
565032
66792
272448
3
12
64
877
0
2
4
32
876

 Код программы

Решение

Вводим поток чисел до тех пор пока не встретим $0$ и проводим над каждым числом следующую операцию.
Вычисляем количество правильных несократимых дробей с помощью функции Эйлера. Занимаемся проверкой числа на простоту. Простой, но медленный метод проверки простоты заданного числа $n$ известен как перебор делителей. Будем проверять, является ли $n$ кратным каждому целому числу от $2$ до  $\sqrt{n}$.
В ходе проверки на простоту находим и другие кратные делители, если таковые имеются. При обнаружение какого то кратного найдем количество несократимым для данного несократимого. Частное, где числитель — это наше число, а знаменатель — определенный кратный делитель, будет количеством сократимых чисел, связанное с текущим кратным делителем. Естественно, если отнимем всё число от делимого, то получим число несократимых.
Повторяем цикл пока обнаруживаются новые кратные нашему числу и с каждым разом уменьшая количество несократимых.

Ссылки

e-olymp 338. Моя любимая, несократимая…

Задача

“Название задачи можно напевать на мотив марша или строевой песни…”

Сколько существует правильных несократимых дробей на промежутке [[latex]0[/latex]..[latex]1[/latex]], знаменатель которых не превышает [latex]n[/latex]?

Входные данные

Натуральное число [latex]n[/latex] ([latex]n < 10001[/latex]).

Выходные данные

Вывести количество правильных несократимых дробей на промежутке [[latex]0..1[/latex]], знаменатель которых не превышает [latex]n[/latex].

Тесты

 

Входные данные Выходные данные
1 0
10000 30397485
5 9
80 1965
37 431
5168 8119803
9973 30237929

Решение задачи

Для решения данной задачи вопользуемся функцией Эйлера [latex] \varphi (n)[/latex], равной количеству натуральных чисел, меньших [latex]n[/latex] и взаимно простых с ним. Очевидно, что количество правильных несократимых дробей со знаменателем [latex]n[/latex] равно [latex] \varphi (n)[/latex]. И тогда количество правильных дробей со знаменателем, не превыщающим [latex]n[/latex] равно [latex] \sum\limits_{i=2}^{n}{\varphi (n)}[/latex] (тут мы учли, что при [latex]i[/latex] = 1 знаменатель дроби равен 1 и дробь не будет правильной).

Ссылки

Условие задачи на сайте  E-Olymp

код задачи на Ideone

описание функции Эйлера на Wikipedia