Các số nguyên tố עד n - JavaScript

Viết hàm nhận số n, trả về mảng tất cả số nguyên tố ≤ n.

Ví dụ

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

Giải pháp

Mã triển khai (kiểm tra nguyên tố cơ bản):

const num = 24;

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

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

console.log(primeUpto(num));

Kết quả

Đầu ra trong console:

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

Tối ưu: Sàng Eratosthenes O(n log log n) cho n lớn.