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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <stdio.h>
int phi(int n) {
int ret = 1;
for(int i = 2; i * i <= n; ++i) {
int p = 1;
while(n % i == 0) {
p *= i;
n /= i;
}
if((p /= i) >= 1) ret *= p * (i - 1);
}
return --n ? n * ret : ret;
}