calculate prime numbers in javascript

To calculate prime numbers in JavaScript, we can use a straightforward approach known as the Sieve of Eratosthenes. This algorithm works by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with 2. The algorithm can be optimized by only searching up to the square root of the maximum number to be checked.

Here is an implementation of the Sieve of Eratosthenes algorithm in JavaScript:


index.tsx
function sieveOfEratosthenes(n) {
  // Create an array of true values up to n (initially all numbers are assumed prime)
  let primes = new Array(n + 1).fill(true);
  // Exclude 0 and 1 from the list of primes
  primes[0] = false;
  primes[1] = false;

  // Iterate over every number up to the square root of n
  for (let i = 2; i <= Math.sqrt(n); i++) {
    // If the current number is prime (i.e., not marked composite)
    if (primes[i] === true) {
      // Mark all of its multiples as composite (since they cannot be prime)
      for (let j = i * i; j <= n; j += i) {
        primes[j] = false;
      }
    }
  }

  // Return an array containing all of the prime numbers up to n
  return primes.reduce((acc, val, idx) => {
    if (val) acc.push(idx);
    return acc;
  }, []);
}
783 chars
25 lines

To use this function, simply call it with the maximum number you want to check. For example:


index.tsx
sieveOfEratosthenes(100); // Returns: [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]
135 chars
2 lines

This implementation has a time complexity of O(n*log(log(n))) and a space complexity of O(n).

similar javascript code snippets

find prime number in javascript

how to extract prime numbers from 0 to 1000 in javascript

prime number in javascript

find the nth prime number in javascript

print the numbers from 1 to 100, but only print the even numbers in javascript

print the numbers from 1 to 100 in javascript

calculate pi plus infinity in javascript

define a function that takes a list of numbers as an argument and returns the sum of the numbers in the list. in javascript

create a function that takes in 3 arguments in javascript

calculate pi in javascript

related categories