การหาตัวเลขที่น้อยที่สุดซึ่งหารด้วยตัวเลข 1 ถึง n ลงตัวใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับตัวเลข n เข้ามา ฟังก์ชันควรหาและคืนค่าตัวเลขที่น้อยที่สุดซึ่งหารด้วยทุกตัวเลขตั้งแต่ 1 ถึง n ลงตัว (Least Common Multiple - LCM)

ตัวอย่าง

โค้ดตัวอย่างด้านล่าง:

const num = 11;
const smallestDivisible = (num = 1) => {
  let res = num * (num - 1) || 1;
  for (let i = num - 1; i >= 1; i--) {
    if (res % i) {
      for (let j = num - 1; j >= 1; j--) {
        if (!(i % j) && !(res % j)) {
          res = i * res / j;
          break;
        }
      }
    }
  }
  return res;
};
console.log(smallestDivisible(num));

ผลลัพธ์

27720

คำอธิบายเพิ่มเติม

โค้ดนี้ใช้หลักการหาตัวคูณร่วมน้อย (LCM) โดยเริ่มจากผลคูณของ n และ n-1 แล้วลดทอนค่าลงเรื่อยๆ โดยการหารด้วยตัวหารร่วมมาก (GCD) วิธีที่มีประสิทธิภาพมากกว่าคือการใช้สูตร LCM(a,b) = a*b/GCD(a,b) แบบสะสม