3-欧拉函数

算法思想

算法模板

public static int phi(int n)
{
	int res = n;
	for(int i = 2; i <= n / i; i ++ )
	{
		if(n % i == 0)
		{
			res = res / i * (i - 1);
			while(n % i == 0) n /= i;
		}
	}
	if(n > 1) res = res / n * (n - 1);

	return res;
}