การหาจำนวนเฉพาะทั้งหมดจนถึง n (Prime Sieve) ใน JavaScript

ภาพรวม

บทความนี้สาธิตวิธีหาจำนวนเฉพาะทั้งหมดตั้งแต่ 2 ถึง n โดยใช้ Trial Division (ไม่ใช่ Sieve of Eratosthenes)

ตัวอย่าง

Input:  24
Output: [2, 3, 5, 7, 11, 13, 17, 19, 23]

การนำไปใช้ (Trial Division)

const isPrime = (num) => {
  if (num < 2) return false;
  let count = 2;
  while (count < (num / 2) + 1) {
    if (num % count !== 0) {
      count++;
      continue;
    }
    return false;
  }
  return true;
};

const primeUpto = (num) => {
  if (num < 2) return [];
  const res = [2];
  for (let i = 3; i <= num; i++) {
    if (isPrime(i)) res.push(i);
  }
  return res;
};

console.log(primeUpto(24));

ผลลัพธ์

[2, 3, 5, 7, 11, 13, 17, 19, 23]

Sieve of Eratosthenes (เร็วกว่ามาก O(n log log n))

const sieveOfEratosthenes = (n) => {
  if (n < 2) return [];
  
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  
  for (let i = 2; i * i <= n; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  
  return isPrime
    .map((prime, index) => prime ? index : -1)
    .filter(x => x !== -1);
};

console.log(sieveOfEratosthenes(24)); // [2, 3, 5, 7, 11, 13, 17, 19, 23]
console.log(sieveOfEratosthenes(1000000).length); // 78498 primes

Segmented Sieve (สำหรับ Range ใหญ่)

const segmentedSieve = (low, high) => {
  const limit = Math.floor(Math.sqrt(high)) + 1;
  const basePrimes = sieveOfEratosthenes(limit);
  
  const isPrime = new Array(high - low + 1).fill(true);
  
  for (const p of basePrimes) {
    const start = Math.max(p * p, Math.ceil(low / p) * p);
    for (let j = start; j <= high; j += p) {
      isPrime[j - low] = false;
    }
  }
  
  if (low === 1) isPrime[0] = false;
  
  return isPrime.map((prime, i) => prime ? low + i : -1).filter(x => x !== -1);
};

การประยุกต์ใช้

• Cryptography: RSA Key Generation
• Hash Tables: Prime Table Sizes
• Random Number Generators
• Competitive Programming
• Number Theory Research

Complexity Comparison