นับจำนวนเฉพาะในช่วง (Prime Numbers in Range) - JavaScript

ฟังก์ชันนับจำนวนเฉพาะ (Prime Numbers) ระหว่างสองจำนวน a และ b (รวมขอบเขต)

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

const isPrime = num => {
  if (num < 2) return false;
  let count = 2;
  while (count <= Math.sqrt(num)) {
    if (num % count === 0) return false;
    count++;
  }
  return true;
};

const primeBetween = (a, b) => {
  let count = 0;
  for (let i = Math.min(a, b); i <= Math.max(a, b); i++) {
    if (isPrime(i)) count++;
  }
  return count;
};

console.log(primeBetween(2, 21));

ผลลัพธ์

8

การปรับปรุงประสิทธิภาพ (Optimization)

// Sieve of Eratosthenes สำหรับช่วงใหญ่
const primeBetweenOptimized = (a, b) => {
  const max = Math.max(a, b);
  const sieve = new Array(max + 1).fill(true);
  sieve[0] = sieve[1] = false;
  
  for (let i = 2; i * i <= max; i++) {
    if (sieve[i]) {
      for (let j = i * i; j <= max; j += i) {
        sieve[j] = false;
      }
    }
  }
  
  let count = 0;
  for (let i = Math.min(a, b); i <= max; i++) {
    if (sieve[i]) count++;
  }
  return count;
};

O(n log log n) เร็วกว่าการตรวจสอบทีละตัว O(n√n) สำหรับช่วงใหญ่