欧拉函数

定义：给定正整数n，小于等于n的正整数之中，有多少个数与n互质

计算个数的公式 欧拉函数，φ(n)表示

证明：

　　1. n = 1， φ(1) = 1 。1与任何数（包括自身）互质

　　2. n为质数， φ(n)=n-1 。质数n与小于n的数互质（除了自身）

　　3. 如果n是质数的次方 n = p^k ( p 为质数，k 为大于等于1的整数)。

　　　因为为p(质数)的k次方，则n的因子只有 p 。

　　　小于(p^k)的数有（p^k - 1)个

　　　所以p的倍数与n皆有（1，p)两个因子，除了p的倍数，其他数都与n互质

　　　所以小于n的数中为p的倍数的个数为：(p^k)/p - 1

　　　所以 φ(n) =  (p^k - 1) - ((p^k)/p - 1)

　　　　　　　  =  p^k - p^k)/p

　　　　　　　  =  p^k - p^(k-1)

　　　　　　　  =  p^k(1 - 1/p)

　　4. n = p * q (p, q互质)

　　　 φ(n) = φ(p*p) = φ(p)*φ(q)

　　5. 任意大于1的n

　　　 n可以写成多个质数次方的积

直接求n的欧拉函数φ(n)

ll Euler(ll n)
{
    ll ans = 1;
    ans = ans * n;
    for(ll i = ; i * i <= 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;

}

View Code

欧拉函数

原文：https://www.cnblogs.com/1998LJY/p/10692803.html