首页 > itarticle > 欧拉函数模板

欧拉函数模板

admin 11月 13, 2020 0

对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）
欧拉函数打表：

const int maxn=5e6+10;
long long phi[maxn];
void phi_table()
{
	memset(phi,0,sizeof(phi));
	phi[1]=1;
	for(int i=2; i <= maxn ; i++){
		if(!phi[i]){
			for(int j=i;j<maxn;j+=i){
				if(!phi[j])	phi[j]=j;
				phi[j]=phi[j]/i*(i-1);
			}
		}
	}
	phi[0]=0;
}