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

Напишите программу, которая вычислит φ(650933)  . φ(n)  – это арифметическая функция (функция Эйлера), значение которой равно количеству натуральных чисел, не превышающих n и взаимно простых с ним.

Нетрудно заметить, что 650933 простое число, а для простых чисел p, очевидно, функция Эйлера равна p — 1 (так как с p взаимнопросты все числа до него).

print(65033-1)

Ладно-ладно, шучу

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
 

 

 
print(phi(650933))

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