有关欧拉函数

有关欧拉函数

欧拉函数：1~N中与N互质的数的个数被称为欧拉函数，记作φ(n) 。

举例　：８的欧拉函数是４（１，３，５，７），５的欧拉函数是４（４，３，２，１）。

欧拉函数的通式：φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn)

　　　　　　　　　        =n*((p1-1)/p1) * ((p2-1)/p2) * ((p3-1)/p3)*((p4-1)/p4)……* ((pn-1)/pn)

其中p1, p2……pn为n的所有质因数，n是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。

欧拉函数的定理（转载）：.html

＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿

根据欧拉函数的计算式，我们只需要分解质因数，即可顺便求出欧拉函数：

int phi(int n)//用于求单个数的欧拉函数
{int ans = n;for (int i = 2; i <= sqrt(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);}return ans;
}

＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿

利用埃氏筛法，我们可以按照欧拉函数的计算式，在（Ｏ(nlogn)）的时间内求出2~N钟每个数的欧拉函数

int phi[1000010];
void euler(int n)
{for (int i = 2; i <= n; i++){phi[i] = i;}for (int i = 2; i <= n; i++){if (phi[i] == i)//表示当前是素数{for (int j = i; j <= n; j += i){phi[j] = phi[j] / i * (i - 1);//根据欧拉公式x(1-1/p1)*(1-1/p2).. 再加上倍数法 }}}
}

最后附上memset的注意事项　以及　欧拉函数的浅谈

memset函数用法及注意事项（转载）：

欧拉函数的浅谈（转载）：=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7EsearchFromBaidu%7Edefault-1.pc_relevant_baidujshouduan&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2%7Edefault%7EsearchFromBaidu%7Edefault-1.pc_relevant_baidujshouduan

初次写博客，如有疏漏不得体，欢迎指出～