牛客网|求最小公倍数

清疚 2022-11-12 14:52 227阅读 0赞

## 题目信息 ##

正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。

**输入描述**: 输入两个正整数A和B，两个数字之间空格隔开

**输出描述**: 输出A和B的最小公倍数。

**输入示例**：5 7

**输出示例**：35

### 题解 ###

求解最小公倍数时，须要对数字分解质因数，然后去除重复的因子，其余因子之积变为最小公倍数。

如 6=2\*3，8=2\*2\*2 ，两个数字分解质因数后，有一个因子2是重复的，去除重复的2，剩余因子之积 3\*2\*2\*2 = 24 便为最小公倍数。

### 编码 ###

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * @最小公倍数
     */
    public class LeastCommonMultiple {
    
    	public static void main(String[] args) throws IOException {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		String input;
    		while ((input = br.readLine()) != null) {
    			String[] arr = input.split(" ");
    			
    			// 定义list，接受最小公倍数拆解出来的因子
    			List<Integer> list = new ArrayList<>();
    			
    			// 将给定的两个数字分解质因数
    			List<Integer> list1 = resolvePrime(Integer.parseInt(arr[0]));
    			List<Integer> list2 = resolvePrime(Integer.parseInt(arr[1]));
    			
    			// 以list1为基准，去除list2中与list1重复的项
    			for (Integer num : list1) {
    				list.add(num);
    				if (list2.contains(num)) {
    					list2.remove(num);
    				}
    			}
    			
    			// 将list2剩余数据项添加到最小公倍数列表中
    			for (Integer num : list2) {
    				list.add(num);
    			}
    			
    			// 循环求出最小公倍数
    			int number = 1;
    			for (Integer num : list) {
    				number *= num;
    			}
    			
    			System.out.println(number);
    		}
    	}
    	
    	/**
    	 * @分解质因数
    	 * @param num
    	 * @return
    	 */
    	public static List<Integer> resolvePrime(int num) {
    		List<Integer> list = new ArrayList<>();
    		int start = 2;
    		
    		// 待数字除的为1时退出
    		while (num > 1) {
    			// 若数字可以整除start，说明start为num的因子
    			// 将商作为新的数字，start置为2
    			// 重新开始循环
    			if (num % start == 0) {
    				num = num/start;
    				list.add(start);
    				start = 2;
    			} else {
    				// 若不能整除，则start加一，继续循环
    				start++;
    			}
    		}
    		return list;
    	}
    }