Skip to content
RSS feed tkhwang on GitHub tkhwang on Twitter

Sieve of Eratosthenes (how to count primes) in javascript

🔥 Algorithm

imgvisual from the wikipedia page on the sieve of Eratosthenes

  • If only check until Math.sqrt(N), you should count the number of primes again.
/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function (N) {
  const seen = Array(N + 1).fill(false);
  let count = 0;

  for (let p = 2; p <= Math.sqrt(N); p += 1) {
    if (seen[p]) continue;

    for (let i = p * p; i < N; i += p) {
      seen[i] = true;
    }
  }

  for (let p = 2; p < N; p += 1) {
    if (!seen[p]) count += 1;
  }

  return count;
};
  • If you check seen[] until N, you can check count in the same for the statement.
var countPrimes = function (N) {
  const seen = Array(N + 1).fill(false);
  let count = 0;

  for (let p = 2; p < N; p += 1) {
    if (seen[p]) continue;

    count += 1;

    for (let i = p * p; i < N; i += p) {
      seen[i] = true;
    }
  }

  return count;
};

💡 Simple algorithm

Sieve of Eratosthenes is good, but sometimes it's ok to use the simplest algorithm.

const isPrime = (num) => {
  for (let i = 2; i <= Math.sqrt(num); i += 1) {
    if (num % i === 0) return false;
  }
  return true;
};

🗒️ Typical problems

📚 References