输入两个正整数,求它们的最大公约数和最小公倍数。

时间:2021-08-10 21:38:51

输入两个正整数,求它们的最大公约数和最小公倍数。


package demo40;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
* 输入两个正整数m和n,求它们的最大公约数和最小公倍数。
*
* @author trust the process
*
*/
public class Demo06 {

public static void main(String[] args) {

System.out.println("======求两正整数的最大公约数与最小公倍数======");

int num1 = 0; // 第一个正整数
int num2 = 0; // 第二个正整数
int maxSubmultiple = 1; // 最大公约数
int minMultiple = 1; // 最小公倍数

Scanner s = new Scanner(System.in); // 键盘输入

System.out.println("请输入第一个正整数:");
num1 = s.nextInt();

System.out.println("请输入第二个正整数:");
num2 = s.nextInt();

// 把num1设为两者中的较小的值
int temp = 0;
if (num1 > num2) {
temp = num1;
num1 = num2;
num2 = temp;
}

// 定义一个集合,用来存放num1的所有质因子
List<Integer> list = new ArrayList<>();

// 求num1的所有质因子,然后存放在list中
test02(num1, list);

// 求最小公倍数
minMultiple = test03(num2, list);
System.out.println("最小公倍数为:" + minMultiple * num2);

// 求最大公约数
maxSubmultiple = test04(num2, list);
System.out.println("最大公约数为:" + maxSubmultiple);

}

public static void test02(int m, List<Integer> primes) {
for (int i = 2; i <= m; i++) {
if (m % i == 0) {
primes.add(i);
test02(m / i, primes);
break;
}
}
}

public static int test03(int m, List<Integer> primes) {
int minNum = 1;
for (int i = 0; i < primes.size(); i++) {
if (m % primes.get(i) == 0) {
m = m / primes.get(i);
} else {
minNum = minNum * primes.get(i);
}
}
return minNum;
}

public static int test04(int m, List<Integer> primes) {
int maxNum = 1;
for (int i = 0; i < primes.size(); i++) {
if (m % primes.get(i) == 0) {
maxNum = maxNum * primes.get(i);
m = m / primes.get(i);
}
}
return maxNum;
}

}

输入两个正整数,求它们的最大公约数和最小公倍数。