利用分解两个数的质因数,找到他们的公共质因数找到他们的最大公约数,java编写
时间: 2024-02-01 11:14:16 浏览: 30
以下是Java代码实现:
```java
import java.util.*;
public class CommonFactor {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("请输入第一个数:");
int num1 = sc.nextInt();
System.out.print("请输入第二个数:");
int num2 = sc.nextInt();
List<Integer> factors1 = factorize(num1);
List<Integer> factors2 = factorize(num2);
Set<Integer> commonFactors = new HashSet<>();
for (int factor : factors1) {
if (factors2.contains(factor)) {
commonFactors.add(factor);
}
}
int gcd = 1;
for (int factor : commonFactors) {
gcd *= factor;
}
System.out.println(num1 + "和" + num2 + "的公共质因数为:" + commonFactors);
System.out.println(num1 + "和" + num2 + "的最大公约数为:" + gcd);
}
// 分解质因数
public static List<Integer> factorize(int num) {
List<Integer> factors = new ArrayList<>();
for (int i = 2; i <= num; i++) {
while (num % i == 0) {
factors.add(i);
num /= i;
}
}
return factors;
}
}
```
代码实现了以下功能:
1. 输入两个整数 `num1` 和 `num2`;
2. 分解 `num1` 和 `num2` 的质因数;
3. 找到 `num1` 和 `num2` 的公共质因数;
4. 计算 `num1` 和 `num2` 的最大公约数(即公共质因数的积)。