Задача к ЕГЭ по информатике на тему «Программирование — Обработка целочисленной информации» №3

Напишите программу, которая вычислит сумму значений функции Эйлера от натуральных делителей числа 9999555.

Как известно, сумма функций Эйлера делителей числа равна самому числу, так что ответ 9999555.

print(9999555)

Ладно-ладно, опять шучу

def gcd(a, b):
 
    if a == b:
 
        return a
 
    if a != 0 and b != 0:
 
        return gcd(a % b, b % a)
 
    else:
 
        return a + b
 

 

 
def phi(n):
 
    fi = 0
 
    for i in range(1, n + 1):
 
        if gcd(n, i) == 1:
 
            fi += 1
 
    return fi
 

 

 
a = 9999555
 
s = 0
 
for i in range(1, int(a ** 0.5) + 1):
 
    if a % i == 0:
 
        s += phi(i)
 
        if i != a // i:
 
            s += phi(a // i)
 
print(s))

Ответ: 9999555
Оцените статью
Я решу все!