欧拉函数定义
1：文字描述:对于正整数n，欧拉函数是小于n的正整数中与n互质的整数的个数。
例如：PHI(2)=1,PHI(3)=2。
所以容易得到素数t的欧拉函数值为t-1
2：公式:PHI(n)=n(1-1/p1)…(1-1/pi)
p1,p2…pi为唯一分解定理中的因数。
(即n=p1^k1 p2^k2 …pi^ki)
欧拉函数的一些性质
欧拉函数是积性函数,当n，m互质时，可以得到：
PHI(nm)=PHI(n)PHI(m)
同时可以得到：
当n为奇数时候PHI(2*n)=PHI(n)
代码实现
//常用欧拉函数打表
int pre[1000000];
void phi(){
memset(pre,0,sizeof(pre));
for(int i=2;i<=1000000;i++){
if(!pre[i]){//当对应数组中存的值为0时，防止重复
for(int j=i;j<=1000000;j+=i){
if(!pre[j])pre[j]=j;//如果开始为0的话赋值
pre[j]=pre[j]/i*(i-1);//套公式
}
}
}
}