Peking University Online Judge 2407 Relatives

オイラーのΦ関数を返すだけ
なぜこの実装でΦ関数が実現できるかを理解することが重要ではないかと（お前誰だよ）

#include<cstdio>
using namespace std;
typedef long long int ll;

ll euler_phi(ll n){
	ll res = n;
	for(ll i = 2; i * i <= n; i++){
		if(n % i == 0){
			res = res / i * (i - 1);
			for(; n % i == 0; n /= i);
		}
	}
	if(n != 1) res = res / n * (n - 1);
	return res;
}

int main(){
	ll n;
	for(;;){
		scanf("%lld", &n);
		if(n == 0) break;
		printf("%lld\n", euler_phi(n));
	}
	return 0;
}