你會求《數字範圍内的最小公倍數》嗎？

這是我參與更文挑戰的第21天，活動詳情檢視： 更文挑戰

今天我在練習FreeCodeCamp的時候，發現一道很有意思的初級算法題目，特地和大家分享一下。

題目描述

找到可以被兩者以及這些參數之間範圍内的所有序列号均分的所提供參數的最小公倍數。

該範圍将是一個由兩個數字組成的數組，不一定按數字順序排列。

例如，如果給定 1 和 3，請找出 1 和 3 的最小公倍數，該倍數也可以被1 和 3之間的所有數字整除。 這裡的答案是 6。

測試執行個體

解題思路

當我剛剛看到這道題目的時候，我在想求最小公倍數這還不簡單？但是事情仿佛沒那麼容易，原因在于題目中讓我們求的不是兩個數字的最小公倍數，而是這個區間範圍内的最小公倍數，是以看懂題目很關鍵。

難點：如何求兩個數的最小公倍數

思路

1. 首先預設兩個數字中較大的那個為最小公倍數。
2. 通過while循環，隻要預設的最小公倍數小于等于兩數的乘積便進入循環，如果這個預設的最小公倍數對左邊的數趨于為零，說明這個是最小公倍數直接傳回即可，反之，讓這個預設的最小公倍數加上右邊的值繼續循環。

代碼

// 擷取最小公倍數的函數
    function getSCM(left, right) {
        // 首先預設最小公倍數為right
        let SCM = right;
        while (SCM <= right * left) {
            if (SCM % left === 0) {
                return SCM
            } else {
                SCM = SCM + right;
            }
        }
    }
複制代碼      

解題代碼

function smallestCommons(arr) {
    arr.sort((next, pre) => next - pre);
    // 擷取最小公倍數的函數
    function getSCM(left, right) {
        // 首先預設最小公倍數為right
        let SCM = right;
        while (SCM <= right * left) {
            if (SCM % left === 0) {
                return SCM
            } else {
                SCM = SCM + right;
            }
        }
    }
    // 生成數組
    const newArr = [];
    for (let i = arr[0]; i <= arr[1]; i++) {
        newArr.push(i);
    }
    let result = arr[0] * (arr[0] + 1);
    // 通過循環不斷更新最小公倍數
    for (let i = 2; i < newArr.length; i++) {
        result = getSCM(newArr[i], result);
    }
    return result;
}
smallestCommons([1, 5]);
複制代碼      

本題給我們的啟示

1. 學會通過循環的方式來求兩個數字的最小公倍數。
2. 學會通過更新的方式來擷取，範圍内的最小公倍數。

參考連結

• 找出數字範圍的最小公倍數