การหาจำนวนเฉพาะที่ใกล้ที่สุดและมากกว่าตัวเลขที่กำหนดใน JavaScript

ภาพรวม

บทความนี้สาธิตวิธีหาจำนวนเฉพาะ (Prime Number) ตัวแรกที่มากกว่าตัวเลขที่กำหนด เช่น 24 -> 29

การนำไปใช้

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

const nearestPrime = (num) => {
  while (!isPrime(++num)) {}
  return num;
};

console.log(nearestPrime(24)); // 29

ผลลัพธ์

29

การปรับปรุงประสิทธิภาพ isPrime

// ตรวจสอบถึง √n แทน n
const isPrimeOptimized = (n) => {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 === 0 || n % 3 === 0) return false;
  
  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) return false;
  }
  return true;
};

// 6k ± 1 Optimization: Prime > 3 เป็นรูป 6k±1

Sieve of Eratosthenes (สำหรับหา Prime หลายตัว)

const sievePrimes = (limit) => {
  const isPrime = new Array(limit + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  
  for (let i = 2; i * i <= limit; i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= limit; j += i) {
        isPrime[j] = false;
      }
    }
  }
  return isPrime;
};

// ใช้สำหรับ nearestPrime หลายครั้ง
const primeCache = sievePrimes(1000000);
const nearestPrimeFast = (num) => {
  for (let i = num + 1; i < primeCache.length; i++) {
    if (primeCache[i]) return i;
  }
  // Fallback ถ้าเกิน Cache
  return nearestPrime(num);
};

Miller-Rabin Primality Test (สำหรับตัวเลขใหญ่)

const isPrimeMillerRabin = (n) => {
  if (n < 2) return false;
  if (n % 2 === 0) return n === 2;
  if (n % 3 === 0) return n === 3;
  
  // Deterministic bases for n < 2^64
  const bases = [2, 325, 9375, 28178, 450775, 9780504, 1795265022];
  
  const d = n - 1;
  let s = 0;
  while (d % 2 === 0) { d /= 2; s++; }
  
  for (const a of bases) {
    if (a % n === 0) continue;
    let x = modPow(a, d, n);
    if (x === 1 || x === n - 1) continue;
    let composite = true;
    for (let r = 1; r < s; r++) {
      x = (x * x) % n;
      if (x === n - 1) { composite = false; break; }
    }
    if (composite) return false;
  }
  return true;
};

const modPow = (base, exp, mod) => {
  let result = 1n;
  base = BigInt(base) % BigInt(mod);
  exp = BigInt(exp);
  mod = BigInt(mod);
  while (exp > 0) {
    if (exp & 1n) result = (result * base) % mod;
    base = (base * base) % mod;
    exp >>= 1n;
  }
  return Number(result);
};

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

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