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}$.
В ходе проверки на простоту находим и другие кратные делители, если таковые имеются. При обнаружение какого то кратного найдем количество несократимым для данного несократимого. Частное, где числитель — это наше число, а знаменатель — определенный кратный делитель, будет количеством сократимых чисел, связанное с текущим кратным делителем. Естественно, если отнимем всё число от делимого, то получим число несократимых.
Повторяем цикл пока обнаруживаются новые кратные нашему числу и с каждым разом уменьшая количество несократимых.

Ссылки

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

    • Сделайте, пожалуйста, дробь так $\frac{m}{n}$.
    • Избегайте ненужных пустых строк. Мне приходится их вычищать. В коде не трогал, но и там в них мало смысла.
    • Избавьтесь от break. Здесь он совсем не нужен.
    • Сделайте правильные отступы.
    • Если всё решение строится на функции Эйлера, то возможно стоит добавить ее в метки?
    • Если всё решение строится на функции Эйлера, то возможно стоит сделать её упоминание гиперссылкой на Википедию? Или, ещё лучше, на e-max откуда Вы позаимствовали основную часть кода. По крайней мере, тогда это будет не совсем плагиат. Уверен, вы не просто скопировали, а полностью разобрались и сможете всё описать.
    • Объяснение слишком лаконичное. Скорее намек. Надо объяснить подробнее.
    • Зачем печатать пустую строку в начале? Нужно просто cout << k << endl;.
  1. Хорошо.
    — Для вставки формул просто в текстовом режиме используйте знак доллара или шорткод latex. Не нужно это делать в визуальном режиме. Или потом аккуратно удаляйте все эти никому не нужные span class=»mwe-math-element» span class=»mwe-math-mathml-inline mwe-math-mathml-a11y».
    — Немного поправил вам стилистику. Если согласны, удалите свой текст. Если нет — мой.
    — Фразу «Делением знаменателя на делитель мы найдем количество сократимых чисел на число, которые мы в данный момент проверяем» я не смог понять. Может стоит ввести буквенные обозначения? После Ньютона и Лейбница описывать решение математических задач стихами стали избегать 🙂

Добавить комментарий