java求最大公约数分解质因数法

### Java 求最大公约数 (GCD) 分解质因数法 #### 简介 在数学中，**最大公约数（Greatest Common Divisor, GCD）**是指两个或多个整数共有的最大的正整数除数。而通过“分解质因数”的方法可以有效地求出任意两数的最大公约数。 #### 步骤解析 1. **找到每个数字的所有质因子**： - 对于给定的两个数 `a` 和 `b`，先将它们各自完全分解成若干个质数相乘的形式。 2. **找出公共质因子及其最小指数**： - 观察这两个数所含有的所有相同的质因子，并取其最低次幂作为结果的一部分。 3. **计算最终结果**： - 将上述得到的所有相同质因子按照步骤二确定好的次数相乘起来就得到了我们想要的结果——即这两者的最大公因数了！ 下面是具体的Java代码示例： ```java import java.util.*; public class GCDFactorization { // 获取某个数值n对应的素因子列表 private static Map<Integer, Integer> primeFactors(int n){ int divisor = 2; Map<Integer, Integer> factors = new HashMap<>(); while(n >= 2){ if(n % divisor == 0){ factors.put(divisor,factors.getOrDefault(divisor, 0)+1); n /=divisor; } else{ ++divisor ; } } return factors; } public static void main(String[] args) { Scanner scanner=new Scanner(System.in); System.out.println("请输入第一个整数:"); int numA=scanner.nextInt(); System.out.println("请输入第二个整数:"); int numB=scanner.nextInt(); // 获得两个数字各自的质因子映射表 Map<Integer,Integer> factorMapA=primeFactors(numA), factorMapB=primeFactors(numB); Set<Integer> commonKeys=new HashSet<>(factorMapA.keySet()); commonKeys.retainAll(factorMapB.keySet()); long gcdResult=(long)1; for(Integer key :commonKeys) gcdResult*= Math.pow(key, Math.min( factorMapA.get(key), factorMapB.get(key))); System.out.printf("%d和%d的最大公约数为：%d%n",numA,numB,gcdResult); } } ``` 此程序首先会提示用户输入一对待比较的整数，然后它分别对这对数字进行了基于试除法的质因数分解操作；最后再对比两者之间的交集部分并累加得出答案。 请注意该算法的时间复杂度取决于所需处理的数据范围大小，在面对非常大的数据量时可能效率不高，但对于日常应用来说已经足够实用啦~