一、欧拉函数

int phi(int n)
{
    int res = n;  // 初始化res=N
    for (int i = 2; i <= n / i; i ++)
        if (n % i == 0)  // 分解质因数
        {
            res = res / i * (i - 1);  // 按照公式计算(p-1)/p
            while (n % i == 0) n /= i;
        }
    if (n > 1) res = res / n * (n - 1);  // 剩余的比根号n还大的质因数
    return res;
}

二、筛法求欧拉函数

将$1$~$n$的数分为：

(1) 质数
(2) 合数
① $i$%$primes[j]=0$的合数
② $i$%$primes[j]≠0$的合数

计算公式：

$Code:$

void get_euler(int n)
{
    euler[1] = 1;
    for (int i = 2; i <= n; i ++)
    {
        if (!st[i])  // 如果这个数没有被标记
        {
            primes[cnt ++] = i;  // 那它就是质数
            euler[i] = i - 1;  // 质数i和前i-1个数均互质，因此φ(i)=i-1
        }
        for (int j = 0; primes[j] <= n / i; j ++)
        {
            int t = primes[j] * i;
            st[t] = true;
            if (i % primes[j] == 0)
            {
                euler[t] = euler[i] * primes[j];
                break;
            }
            euler[t] = euler[i] * (primes[j] - 1);
        }
    }
}