การหาตัวประกอบเฉพาะของตัวเลขใน JavaScript

ภาพรวม

บทความนี้สาธิตวิธีเขียนฟังก์ชัน JavaScript เพื่อหาตัวประกอบเฉพาะ (Prime Factors) ของตัวเลขที่กำหนด ฟังก์ชันจะคืนค่าเป็นอาร์เรย์ที่ประกอบด้วยจำนวนเฉพาะทั้งหมดที่หารตัวเลขนั้นลงตัว

ตัวอย่าง

หากตัวเลขนำเข้าคือ 105 ผลลัพธ์ที่คาดหวังคือ [3, 5, 7] เนื่องจาก 105 = 3 × 5 × 7

การนำไปใช้

const num = 105;

const isPrime = (n) => {
  for (let i = 2; i <= n / 2; i++) {
    if (n % i === 0) return false;
  }
  return true;
};

const findPrimeFactors = (num) => {
  const res = num % 2 === 0 ? [2] : [];
  let start = 3;
  while (start <= num) {
    if (num % start === 0 && isPrime(start)) {
      res.push(start);
    }
    start++;
  }
  return res;
};

console.log(findPrimeFactors(18)); // [3]
console.log(findPrimeFactors(105)); // [3, 5, 7]

ผลลัพธ์

[3, 5, 7]

คำอธิบายโค้ด

• isPrime(n): ตรวจสอบว่า n เป็นจำนวนเฉพาะหรือไม่ โดยลูปตรวจสอบตัวหารจาก 2 ถึง n/2
• findPrimeFactors(num): เริ่มตรวจสอบจาก 2 (ถ้าหารลงตัวเพิ่มเข้าไป) แล้วตรวจสอบเลขคี่ตั้งแต่ 3 ขึ้นไป จนกว่าจะครบตัวเลขทั้งหมด

ข้อควรพิจารณาปรับปรุง

อัลกอริทึมนี้สามารถปรับปรุงประสิทธิภาพได้โดย:

1. ตรวจสอบตัวหาร רק עד √n แทนที่จะเป็น n/2
2. ใช้ Sieve of Eratosthenes สำหรับการหาจำนวนเฉพาะหลายครั้ง
3. หารตัวเลขต้นทางด้วยตัวประกอบที่พบไปเรื่อยๆ เพื่อลดขอบเขตการค้นหา