给定任意正整数
计算这个值的方法就叫做欧拉函数
分析
情况一
如果
情况二
如果
情况三
如果
比如
这是因为只有当一个数不包含质数
即
上面的式子还可以写成下面的形式：
可以看出，上面的第二种情况是
情况四
如果n可以分解成两个互质的整数之积：
则：
即积的欧拉函数等于各个因子的欧拉函数之积。比如
对于素数
欧拉函数是积性函数，但不是完全积性函数
欧拉函数的积性
若
由“
其中
所以
所以
所以
以上部分涉及到“中国剩余定理”
情况五
因为任意一个大于1的正整数，都可以写成一系列质数的积。（分解质因数）
根据结论四，得到
再根据结论三，得到
也就等于
结论
比如
即
对于一个正整数
除了
设
欧拉函数
根据性质二，我们可以在
//直接求解欧拉函数
int euler(int n) { //返回euler(n)
int res = n, a = n;
for (int i = 2; i * i <= a; i++) {
if (a % i == 0) {
res = res / i * (i - 1);//先进行除法是为了防止中间数据的溢出
while (a % i == 0) a /= i;
}
}
if (a > 1) res = res / a * (a - 1);
return res;
}欧拉函数线性筛
如果要求
const int MAXN = 1e6;
//欧拉线性筛：在线性时间内筛素数的同时求出所有数的欧拉函数
int tot;
int phi[MAXN]; //保存各个数字的欧拉函数
int prime[MAXN]; //按顺序保存素数
bool mark[MAXN]; //判断是否是素数
void get_phi(int N){
phi[1] = 1;
for(int i = 2; i <= MAXN; i++){ //相当于分解质因数的逆过程
if(!mark[i]){
prime[++tot] = i;
phi[i] = i-1;
}
for(int j = 1; j <= tot; j++){
if(i * prime[j] > N) break;
mark[i * prime[j]] = 1; //确定i*prime[j]不是素数
if(i % prime[j] == 0){ //判断prime[j] 是否为 i的约数
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
else{ //prime[j] - 1 就是 phi[prime[j]],利用了欧拉函数的积性
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
}