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

Определение

Функция Эйлера $phi (n)$ — это количество чисел от $1$ до $n$, взаимно простых с $n$, т.е. это количество таких натуральных чисел из отрезка [1; n], наибольший общий делитель (НОД) которых с $n$ равен единице.

Первые значения этой функции:

$n$	1	2	3	4	5	6	7	8	9	10
$phi(n)$	1	1	2	2	4	2	6	4	6	4