超棒的欧拉函数讲解：https://blog.csdn.net/ydd97/article/details/47805419

下面的大部分都是借鉴这位大佬的，加了点自己的理解。

 

我就比较懒，直接贴代码了。（讲解都在注释中）

/*
欧拉函数的作用：用于求小于n的与n互质数的个数 
欧拉函数的公式： φ(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn),
其中p1, p2……pn为n的所有质因数，n是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。

1-1/pi = (pi-1)/pi 
*/
const int N = 100010;

int Euler(int n){
	int ans = n;
	for(int i = 2; i * i <= n; i++){
		if(n % i == 0){ 
			ans -= ans / i;
			while(n % i == 0)
				n /= i;
		} 
	}
	if(n > 1) ans -= ans / n;
	
	return ans;	
}

//欧拉函数打表 	 
//这里仍然使用了唯一分解定理的思想，即所有大于2的整数数都可分解为素数的乘积 
void EulerMeter(){
	for(int i = 1; i < N; i++)
		phi[i] = i;//初始化所有数都为i，即上方公式中的n 
	for(int i = 2; i < N; i++)
		if(i == phi[i])//此时i是素数 
			for(int j = i; j < N; j += i)//此时将素数i的所有倍数全部运用一下欧拉公式中的n*(pi-1)/pi,在这里即phi[j] = phi[j] / i * (i - 1) 
				phi[j] = phi[j] / i * (i - 1);
				
				
}