参考代码:
// 欧拉函数: φ(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; } }
0.0分
0 人评分
2006年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:468 |
C语言训练-计算t=1+1/2+1/3+...+1/n (C语言代码)浏览:868 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:1036 |
简单的a+b (C语言代码)浏览:631 |
WU-格式化数据输出 (C++代码)浏览:1212 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:640 |
杨辉三角 (C语言代码)浏览:484 |
用筛法求之N内的素数。 (C语言代码)浏览:529 |
简单的a+b (C语言代码)浏览:630 |
简单的a+b (C语言代码)浏览:830 |