// 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
*/