【最小公倍数LCM】通俗理解以及Java代码实现

什么最小公倍数（Least Common Multiple）

最小公倍数（LCM）是指两个或多个整数共有的最小正倍数，即是这些数的公倍数中最小的一个。计算最小公倍数常常用于问题如合并分数、时间单位的转换等。

最小公倍数计算方法

1. 分解质因数法： 将每个数分解质因数，然后取各数中各质因数的最高次幂，相乘即为最小公倍数。

   例如：计算12和18的最小公倍数。

   • 12的质因数分解为2^2 * 3，18的质因数分解为2 * 3^2。
   • 取各质因数的最高次幂，得到2^2 * 3^2 = 36。

2. 使用最大公约数： 最小公倍数等于两数乘积除以它们的最大公约数。如果不清楚什么是最大公约数请移步https://blog.csdn.net/m0_59167353/article/details/134952218?spm=1001.2014.3001.5502

   例如：计算15和25的最小公倍数。

   • 15和25的最大公约数为5。
   • 最小公倍数 = (15 * 25) / 5 = 75。

通过这些方法，我们可以计算得到两个或多个数的最小公倍数。

用代码实现最小公倍数

public int lcm(int m,int n){ //求最小公倍数
        int M = m,N = n;
        while(n != 0){
            int r = m % n;
            m = n;
            n = r;
        }
        return M * N / m;
    }

JAVA练习最小公倍数为 K 的子数组数目（最大公约数法）

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的 子数组 中满足 元素最小公倍数为 k 的子数组数目。

子数组 是数组中一个连续非空的元素序列。

数组的最小公倍数 是可被所有数组元素整除的最小正整数。

示例 1 ：

输入：nums = [3,6,2,7,1], k = 6
输出：4
解释：以 6 为最小公倍数的子数组是：
- [3,6,2,7,1]
- [3,6,2,7,1]
- [3,6,2,7,1]
- [3,6,2,7,1]

示例 2 ：

输入：nums = [3], k = 2
输出：0
解释：不存在以 2 为最小公倍数的子数组。

class Solution {
  public int subarrayLCM(int[] nums, int k) {
        int num = 0;
        for(int i = 0;i < nums.length;i++){
        	int flag = nums[i];
        	if(flag == k) num++;
	        for (int j = i + 1; j < nums.length; j++) {
                flag = lcm(flag,nums[j]);
				if(flag == k) {
					num++;
				}
                if(flag > k){ //当计算出来的最小公倍数比所给最小公倍数k大时退出内层循环
                    break;
                }
				
			}
        }      
	        return num;   
	    }
    public int lcm(int m,int n){ //求最小公倍数
        int M = m,N = n;
        while(n != 0){
            int r = m % n;
            m = n;
            n = r;
        }
        return M * N / m;
    }
}