หาตัวประกอบเฉพาะทั้งหมดของตัวเลข - JavaScript

หาตัวประกอบเฉพาะ (Prime Factors) ของตัวเลข คือจำนวนเฉพาะที่หารตัวเลขนั้นลงตัว

ตัวอย่าง

18 = 2 × 3 × 3 → Prime Factors: [2, 3]

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

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

const findPrimeFactors = num => {
  const res = num % 2 === 0 ? [2] : [];
  let factor = 3;
  while (factor <= num) {
    if (num % factor === 0 && isPrime(factor)) {
      res.push(factor);
    }
    factor += 2; // ข้ามเลขคู่
  }
  return res;
};

console.log(findPrimeFactors(18));

ผลลัพธ์

[2, 3]

วิธีที่มีประสิทธิภาพมากกว่า (Trial Division)

const findPrimeFactors = num => {
  const factors = [];
  let n = num;
  
  for (let i = 2; i * i <= n; i++) {
    while (n % i === 0) {
      factors.push(i);
      n /= i;
    }
  }
  if (n > 1) factors.push(n);
  return [...new Set(factors)]; // unique only
};

วิธีนี้หารจนกว่าจะไม่ลงตัว แล้วค่อยเพิ่มตัวหาร ลดการตรวจสอบ isPrime ซ้ำ