欧拉函数模板

参考代码:

// 欧拉函数：  φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)
// 对于任意两个互质的正整数m和n，有φ(mn) = φ(m) * φ(n)。（奇性函数）
// 如果n是质数p，则φ(p) = p - 1，即除去p自身外，所有小于p的数都与p互质。

import java.util.Scanner;

public class Main
{   public static void main(String[] args)
    {   Scanner scanner = new Scanner(System.in);
        System.out.print(euler_phi(scanner.nextInt()));
        scanner.close();
    }
    static int euler_phi(int x)
    {   int n = (int)Math.sqrt(x + 0.1);
        //这里使用x + 0.1是为了向上取整，确保不会漏掉任何可能的因数。
        //因为欧拉函数只需要考虑x的质因数及其幂次，所以仅需检查到n即可，这样可以减少不必要的循环次数，提高算法效率
        int res = x;
        //对答案的初始化将其设置为x，因为在遍历因数之前，假设x没有因数，其欧拉值就是它本身。
        for(int i = 2; i <= n; i++)
        {   if(x % i == 0)//找因数
            {   res = res / i * (i - 1);
                while(x % i == 0)//去除重复因数
                    x /= i;
            }
        }
        if(x > 1)//处理剩余的质因数（若存在）
            res = res / x * (x - 1);
        return res;
    }
}