Generate N Prime Numbers (JavaScript)

Generate N Prime Numbers

Generating a list of prime numbers up to a certain limit (N) or generating the first N prime numbers is a common problem in computational number theory. This problem introduces more advanced algorithms than just checking a single prime.

Understanding the Concept

We want to find all prime numbers within a given range or a specific count. The challenge is to do this efficiently, especially for large values of N.

Common Approaches

1. Simple Iteration with Primality Test:

This approach uses the `isPrime` function (from the previous topic) and iterates through numbers, adding primes to a list until N numbers are found or the limit is reached.

Copy to Clipboard

Explanation:

It iterates from 2 up to limitN.
For each number, it calls the `isPrime` function.
If the number is prime, it's added to the `primes` array.
This method can be inefficient for very large `limitN` because `isPrime` is called repeatedly for many numbers.

2. Sieve of Eratosthenes (More Efficient for Primes Up to N):

The Sieve of Eratosthenes is an ancient and very efficient algorithm for finding all prime numbers up to a specified integer. It works by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2.

Copy to Clipboard

function generatePrimesSieve(limitN) {
  if (limitN < 2) {
    return [];
  }

// Create a boolean array 'isPrimeArray[]' and initialize all entries it as true.
  // A value in isPrimeArray[i] will finally be false if i is not a prime, else true.
  const isPrimeArray = new Array(limitN + 1).fill(true);
  isPrimeArray[0] = false; // 0 is not prime
  isPrimeArray[1] = false; // 1 is not prime

// Start from p = 2.
  for (let p = 2; p * p <= limitN; p++) {
    // If isPrimeArray[p] is still true, then it is a prime
    if (isPrimeArray[p] === true) {
      // Mark all multiples of p as false (not prime)
      // Start from p*p because smaller multiples (like 2*p, 3*p) would have already been marked by smaller primes.
      for (let multiple = p * p; multiple <= limitN; multiple += p) {
        isPrimeArray[multiple] = false;
      }
    }
  }

// Collect all prime numbers
  const primes = [];
  for (let i = 2; i <= limitN; i++) {
    if (isPrimeArray[i] === true) {
      primes.push(i);
    }
  }

return primes;
}

// Example usage:
// console.log(generatePrimesSieve(20));  // Output: [2, 3, 5, 7, 11, 13, 17, 19]
// console.log(generatePrimesSieve(30));  // Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Explanation:

An array `isPrimeArray` is created, initially marking all numbers from 0 to `limitN` as potentially prime (`true`).
It iterates from `p = 2` up to `sqrt(limitN)`.
If `isPrimeArray[p]` is `true`, `p` is a prime number. All multiples of `p` (starting from `p*p`) are then marked as `false`.
Finally, numbers whose `isPrimeArray` entry remains `true` are collected as primes.

Key Takeaways

Sieve of Eratosthenes: Highly efficient for finding all primes up to a given limit.
Trade-off: The Sieve uses more memory (an array of booleans) but significantly reduces computation time compared to repeatedly calling `isPrime`.
Optimization: Starting marking multiples from `p*p` is an important optimization for the Sieve.