Плюсануть
Поделиться
Класснуть
Запинить


Олимпиадный тренинг

Вы можете самостоятельно решать эти задачи столько раз, сколько вам это понадобится.
   

Несократимые дроби

Арифметические алгоритмы Функция Эйлера

Дробь m/ n называется правильной несократимой, если 0 < m < n и НОД (m, n) = 1. Найдите количество правильных несократимых дробей со знаменателем n.
 
Входные данные
В первой строке задается число знаменателей для которых надо найти количество правильных несокртимых дробей N (N <=100). Каждая последующая строка число n (n < 109). 
 
Выходные данные
Для каждого n в отдельной строке вывести ответ на поставленную задачу.

Ввод Вывод
4
23
23456
7
17
 
22
11712
6
16

Сумма функции Эйлера

Функция Эйлера

Посчитать сумму функций Эйлера вида: φ(1) + φ(p) + φ(p2) + ... + φ(pα)

где  p (простое число), а-  натуральные числа: ( p <=11,   а  <=60 )