>>358
ひとまず・・・。

unsigned gcd(int x, int y)
{
　unsigned i = x >= 0 ? x : -x;
　unsigned j = y >= 0 ? y : -y;
　if (i < j) {
　　unsigned t = i;
　　i = j;
　　j = t;
　}
　while (j) {
　　unsigned k = j;
　　j = i % j;
　　i = k;
　}
　return i;
}

int psi(int n)
{
　int r = 0, i;
　for (i = 1; i < n; i++)
　　if (gcd(i, n) == 1)
　　　r++;
　return r;
}