How to calculate and print the first 21,000 prime numbers in JavaScript

1 Answer

0 votes
// Calculate and print the first 21,000 prime numbers
// --------------------------------------------------
// This program uses a segmented sieve approach.
// The idea:
//   1. First generate a small list of base primes up to sqrt(limit).
//   2. Then process the number range in segments, marking composites.
//   3. Collect primes until we reach the desired count.
//
// This avoids allocating a huge array all at once and keeps memory usage reasonable.
// It also stays fast because each segment is handled efficiently.

// --------------------------------------------------
// Utility: simple sieve to generate base primes up to a given limit.
// These base primes are used to mark composites in each segment.
function generateBasePrimes(limit) {
  const sieve = new Uint8Array(limit + 1); // 0 = prime candidate, 1 = composite
  const primes = [];

  for (let n = 2; n <= limit; n++) {
    if (!sieve[n]) {
      primes.push(n);
      // Mark multiples
      for (let m = n * n; m <= limit; m += n) {
        sieve[m] = 1;
      }
    }
  }

  return primes;
}

// --------------------------------------------------
// Main prime generator using segmented sieve.
// targetCount: how many primes we want (21,000)
// segmentSize: how large each segment should be (tunable)
function generatePrimes(targetCount, segmentSize = 100000) {
  const primes = [];

  // We don't know how far we need to go, but 21,000 primes end around ~235,000.
  // We'll just keep generating segments until we reach the target.
  let segmentStart = 2;

  // Precompute base primes up to sqrt of a safe upper bound.
  // sqrt(300,000) ≈ 550, so we generate base primes up to 600.
  const basePrimes = generateBasePrimes(600);

  while (primes.length < targetCount) {
    const segmentEnd = segmentStart + segmentSize - 1;

    // Segment array: 0 = prime candidate, 1 = composite
    const segment = new Uint8Array(segmentSize);

    // Mark composites using base primes
    for (const p of basePrimes) {
      // Find the first multiple of p within this segment
      let start = Math.ceil(segmentStart / p) * p;
      if (start < p * p) start = p * p; // ensure we start at p^2

      // Mark multiples
      for (let m = start; m <= segmentEnd; m += p) {
        segment[m - segmentStart] = 1;
      }
    }

    // Collect primes from this segment
    for (let i = 0; i < segment.length && primes.length < targetCount; i++) {
      const n = segmentStart + i;
      if (n >= 2 && !segment[i]) {
        primes.push(n);
      }
    }

    segmentStart = segmentEnd + 1; // move to next segment
  }

  return primes;
}

// --------------------------------------------------
// Run the generator and print the results
const COUNT = 21000;
const primes = generatePrimes(COUNT);

// Print them (you can redirect output or format differently if needed)
console.log(`Generated ${COUNT} primes:`);
console.log(primes.join(", "));


/*
run:

Generated 21000 primes: 

First primes:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,...

Last primes:
237011, 237019, 237043, 237053, 237067, 237071, 237073, 237089, 237091, 237137, 237143, 237151, 237157, 237161, 237163, 237173, 237179, 237203

*/

 



answered May 14, 2016 by avibootz
edited Aug 19 by avibootz
...