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; }