一文读懂欧拉函数

来自：ivy-endhttp://www.ivy-end.com/archives/1021欧拉函数φ(N)表示小于或等于N的正整数中与N互质的数的个数。又称φ函数、欧拉商数。下面介绍欧拉函数的几个性质：我们根据这几个性质就可以求出欧拉函数。基本思路是首先置φ(N)=N，然后再枚举素数p，将p的整数倍的欧拉函数φ(kp)进行如下操作。代码如下：#includeusing namespace std;const int MAX = 1024;int N;int p[MAX], phi[MAX];int main(){    cin >> N;    for(int i = 1; i N; i++)// 初始化    { p[i] = 1; phi[i] = i; }    p[1] = 0;// 1不是素数    for(int i = 2; i N; i++)// 筛素数    {        if(p[i])        {            for(int j = i * i; j N; j += i)            { p[j] = 0; }        }    }    for(int i = 2; i N; i++)// 求欧拉函数    {   ………………………………