🎈三种关于不同需求的欧拉函数求法

第一种方法：连续区间欧拉函数，时间慢，空间小。
第二种方法：连续区间欧拉函数，时间快，空间大。
第三种方法：单个数求欧拉函数，时间快，空间小。

第一种方法：埃氏筛法(时间换空间的方法) 时间复杂度O(n ln ln n)

仅用一个数组空间为S(N) 时间复杂度为O(n*ln ln n);
摘抄于此处

void euler(int n)
{
    for (int i=1;i<=n;i++) phi[i]=i;

    for (int i=2;i<=n;i++)
    {
        if (phi[i]==i)//这代表i是质数
        {
            for (int j=i;j<=n;j+=i)
            {
                phi[j]=phi[j]/i*(i-1);
                //把i的倍数更新掉
                //因为该数 j 为质数的倍数 所以质因子只有该质数 i
                //通过 在 1 到 该质数 j 中， 去除所有 i 的倍数
                //所以phi[j] - phi[j]/i;
            }
        }
    }
}

第二种方法：欧拉筛法(空间换时间方法) 时间复杂度O(n);

虽然空间复杂度达到了S(3*N) 但是时间复杂为 O(n);
摘抄与此处

void euler(int n)
{
   for(int i = 2; i <= n; ++ i)
   {
       if(!st[i]) 
       {
           primes[++ cnt] = i;
           phi[i] = i-1;
       }
       for(int j = 1; primes[j] <= n/i; ++ j)
       {
            int p = primes[j];
            st[ i*p ] = true;
            if(i%p == 0)
            {
                phi[ i*p ] = phi[i] * p;
                //根据欧拉函数的求法：N*(1-1/p1)*(1-1/p2)...*(1-1/pn);
                //而当i%P==0时，p为i的最小质因子，因为根据上式可知，求欧拉函数只与质因子是谁有关，与指数的大小无关，所以仅需将上式的N更新即可。
                break;
            }
            phi[ i*p ] = phi[i] * ( P-1 ); 
            //同理，由于p并非i的质因子，所以需要加一个质因子，公式为phi[i]*(1-1/p)*p 化简后得：phi[i]*(p-1);
       }
   }
}

第三种方法： 求单个数的欧拉函数 时间复杂度 O( $\sqrt{n}$ )

时间复杂度 O(log n) 空间复杂度 S(1);
参考代码

/*
总的做法就是：
   将res存储c; 然后查找c的所有约数，即能整数res的数，全部去除。 
    剩下的便是与c互质的数。
*/
int euler(int c) 
{
    int res = c;
    for (int i = 2; i <= c/i; ++ i)
    {
        if (c % i == 0)//查找c的约数
        {
            while (c % i == 0)  c /= i
            //在c中除约数i。

            res = res / i * (i - 1);
            //由 res = res - res/i; 得来。
            //求不能约去的数的个数。
        }
    }
    if (c > 1) res = res / c * (c - 1);
    //当c还有剩余，则是大于 c^(1/2) 的那个约数，将他在答案中除去。
    return res;
}