欧拉函数

\(updata : 2022.2.2\)

学习原文

求单个欧拉函数

int PHI(int n){
	//int ans = 1;
	int ans = n //注意初值是 n.
	for(int i=2;i*i<=n;++i){
		if(n % i == 0){
			ans = ans/i*(i-1);//先除后乘.
			while( n%i == 0) n /= i;
		}
	}
	if(n > 1) ans = ans/n*(n-1); //参考 2 的例子.
	return ans;
}

线性求 1~n 的欧拉函数

int PHI(int n){
	memset(is_pri,1,sizeof(is_pri));
	is_pri[1] = 0 , phi[1] = 1;
	for(int i=2;i<=n;++i){
		if(is_pri[i]){
			Q[++l] = i;
			phi[i] = i-1;
		}
		for(int j=1;j<=l && Q[j]*i<=n;++j){
			if(i % Q[j]){
				is_pri[ i*Q[j] ] = 0;
				phi[ i*Q[j] ] = phi[i] * Q[j]; //注意积性函数的性质在两者互质时才能用.
			}
			else{
				is_pri[ i*Q[j] ] = 0;
				phi[ i*Q[j] ] = Q[j]*phi[i];
				break;
			}
		}
	}
}