การหาจำนวนเฉพาะถึง n - JavaScript

คืนอาร์เรย์ของจำนวนเฉพาะทั้งหมดตั้งแต่ 2 ถึง n

ตัวอย่าง

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

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

const num = 24;

const isPrime = num => {
  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)) continue;
    res.push(i);
  }
  return res;
};

console.log(primeUpto(num));

การปรับปรุง: Sieve of Eratosthenes (O(n log log n))

const primeUpto = n => {
  if (n < 2) return [];
  const sieve = new Array(n + 1).fill(true);
  sieve[0] = sieve[1] = false;

  for (let i = 2; i * i <= n; i++) {
    if (sieve[i]) {
      for (let j = i * i; j <= n; j += i) {
        sieve[j] = false;
      }
    }
  }
  return sieve.map((isPrime, i) => isPrime ? i : null).filter(x => x !== null);
};

ผลลัพธ์

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