中文
devexamples

Prime Sieve Of Eratosthenes Segmented (JavaScript)

Generate all primes up to n using a segmented sieve of Eratosthenes for memory efficiency on large ranges.

JavascriptData Integrity

Code

snippet
function segmentedSieve(n) {
  if (n < 2) return [];
  const limit = Math.floor(Math.sqrt(n)) + 1;
  const basePrimes = [];
  const isComp = new Array(limit).fill(false);
  for (let i = 2; i < limit; i++) {
    if (!isComp[i]) { basePrimes.push(i); for (let j = i * i; j < limit; j += i) isComp[j] = true; }
  }
  const primes = [...basePrimes];
  const segSize = 1 << 15;
  for (let low = limit; low <= n; low += segSize) {
    const high = Math.min(low + segSize - 1, n);
    const seg = new Array(high - low + 1).fill(false);
    for (const p of basePrimes) {
      let start = Math.ceil(low / p) * p;
      for (let j = start; j <= high; j += p) seg[j - low] = true;
    }
    for (let i = 0; i < seg.length; i++) if (!seg[i] && low + i >= 2) primes.push(low + i);
  }
  return primes;
}

Related Examples