数学·Euler函数·证明及其求法

大家好，欢迎来到IT知识分享网。

欧拉函数是求解n以内和n互质的数的个数的函数。

性质1· Euler（mn） = Euler(m) * Euler(n);

性质2· Euler（m^n） = m^n – m^(n-1) = m^n * (1 – 1/m);

性质3· n = p1^k1 * p2^k2 * p3^ k3 ……..;

综上可知：

Euler(n)= Euler（p1^k1 * p2^k2 * p3…..）;

p1,p2,p3,..为n的质因数；

某犇博客：想点就点

求法：

（1） 直接线性：

int Euler(int n) { int res = n; int a = n; for (int p = 2; p < n; p ++) { if (n % p == 0) { res = res/p *(p-1); while(n%p == 0) { n /= p; } } } if (a > 1) { res = res/a * (a-1); } return res; }

（2） 筛法：

int eul[maxn]; int Euler() { for (int i = 2; i < maxn; i++) { eul[i] =i; } for (int i = 2; i < maxn; i++) { if (eul[i] == i) { for (int j = i; j < maxn; j += i) { eul[i] = euler[j]/i * (i-1); } } } }