欧拉函数及其相关性质的证明

int phi(int x){//求x的欧拉函数值
	int ans=x;
	for(int i=2;i*i<=x;i++){//分解x的质因数
		if(x%i==0){
			ans=ans/i*(i-1);
			while(x%i==0){
				x/=i;
			}	
		}
	}
	if(x>1) ans=ans/x*(x-1);
	return ans;
}

int erla(int n){//利用线性筛更新欧拉函数值
	int cnt=0;//质数个数
	v[0]=v[1]=1;//标记0和1为非质数
	phi[1]=1;//记录1的欧拉函数值为1
	for(int i=2;i<=n;i++){//遍历2~n
		if(!v[i]){//i是质数
			prime[cnt++]=i;//存储i到质数表
			phi[i]=i-1;//性质3： p是质数，phi(p)=p-1
		}
		//遍历质数表
		for(int j=0;j<cnt&&prime[j]*i<=n;j++){
			v[prime[j]*i]=1;//标记质数与i的乘积为非质数
			if(i%prime[j]==0){//性质4:若p%i==0,phi(i*p)=p*phi(i)
				phi[i*prime[j]]=prime[j]*phi[i];
				break;
			}else{//性质5:若p%i!=0,phi(i*p)=(p-1)*phi(i)
				phi[i*prime[j]]=(prime[j]-1)*phi[i];
			}
		}
	}
	return cnt;//返回质数个数
}