欧拉函数

  欧拉函数,它又称为Euler's totient function、φ函数、欧拉商数等,对正整数n，欧拉函数是小于n且和n互质的正整数(包括1)的个数。例如Euler(8)=4，因为1,3,5,7均和8互质,下面用E(n)表示欧拉函数的值。

  Euler函数表达通式：E(x)=x*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…(1-1/pn),其中p1,p2……pn为x的所有素因数，x是不为0的整数。E(1)=1（唯一和1互质的数就是1本身）。
  欧拉公式的延伸：一个数的所有质因子之和是 E(n)*n/2。
  欧拉定理：对于互质的正整数a和n，有a^E(n) ≡ 1 mod n。
  欧拉函数是积性函数——若m,n互质，E(m*n)=E(m)*E(n)。
  若n是质数p的k次幂，E(n)=p^k-p^(k-1)=(p-1)*p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
  特殊性质：当n为奇数时，E(2n)=E(n)

先是直接根据公式求欧拉函数的值：

//euler(x) = x*(1 - 1/p1)*(1 - 1/p2)*(1 - 1/p3)...(1 - 1/pn)   p1 p2..是x的所有的质因子且各不相同  x != 0
//**质因子之和是euler(x)*x / 2
#include <iostream>

using namespace std;

int Euler(int n)
{
    int res = n , a = n;
    for(int i = 2 ; i*i <= a ; i++)
    {
        if(a % i == 0)  //i一定是素数
        {
            res = res / i * (i - 1);  //根据公式
            while(a % i == 0)  //把相同的除数排除
            {
                a /= i;
            }
        }
    }
    if(a > 1)  //最后只剩下 小于4的素数  或者n本身就是素数
        res = res / a *(a - 1);
    return res;
}

int main()
{
    int n;
    while(cin >> n)
    {
        cout << Euler(n) << endl;
    }
}

显然当n比较大的时候用打表访问比较快，下面是筛选法打欧拉函数表 

//离线打表
//筛选法求欧拉函数，时间复杂度O(nloglogn)
//跟埃式筛法求素数差不多
#include <iostream>

using namespace std;

const int MAXN = 100010;
int a[MAXN];

void init()
{
    for(int i = 1 ; i <= MAXN ; i++)
        a[i] = i;
    a[1] = 0;
    for(int i = 1 ; i <= MAXN ; i++)
    {
        if(a[i] == i)
        {
            for(int j = i ; j <= MAXN ; j += i)
                a[j] = a[j] / i * (i - 1);
        }
    }
}

int main()
{
    init();
    int n;
    while(cin >> n)
    {
        cout << a[n] << endl;
    }
}