Breaking Down DSAs: Count Primes

Welcome back! All week I've been trying to think of a blog post idea that wasn't another algorithm breakdown, but yesterday I encountered a crazy cool one that I just want to talk about! The problem comes from the LeetCode collection that I've been working through, and it's called count primes.

Here's the problem: return the number of prime numbers less than a given integer, n. So given 10, the function should return 4, as there are 4 prime numbers less than 10: 2, 3, 5, and 7.

First, I had to refresh my memory on what a prime number even is (don't judge me). A quick google search told me that a prime number is a whole number greater than 1 whose only factors are 1 and itself. I also learned that a non-prime number is called a composite number! Fascinating.

My first attempt (in JavaScript) was pretty straightforward. I created a helper function, isPrime that simply accepts a number and returns a boolean. This function uses a for loop to iterate through every number from 2 up to the given number. I used the modulo/remainder operator to check if the given number divided by the current number in the loop has a remainder of 0. If it does, that means the number is not prime so we can return false. Otherwise, the function returns a boolean from n > 1, to weed out 0 and 1.

function isPrime(n) {
  for (let i = 2; i < n; i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return n > 1;
}

Now my countPrimes function can use my helper to, well, count the primes. I initiated a counter at 0, and since we want to count all the prime numbers less than the given number n, I subtract one from n before I start a while loop. The loop passes n into the helper, and if it returns true, I iterate the counter. I then decrement n, and do it all again, returning the final primesCount at the end. Here's what that all looks like:

function countPrimes(n) {
  let primesCount = 0;
  n--;
  while (n > 1) {
    if (isPrime(n)) {
      primesCount++
    }
    n--;
  }
  return primesCount;
};

Phew! I was feeling pretty good, but I knew there had to be a better way. It's just not efficient to check if every single number is prime, as doing so involves dividing the number by every single number less than it. That's a lot of checks! After failing to think of a more efficient solution, I turned to my trusty friend, Google.

So here's where it gets crazy cool! I learned about the Sieve of Eratosthenes and my mind was blown. This algorithm essentially starts at the first prime number, 2, and marks its multiples as composite (not prime). It then moves onto the next prime, and so on, until reaching the given limit.

I understood how the algorithm worked but I still wasn't sure about the best way to implement it in JavaScript. Some more googling led me to this great post from Nic Raboy.

The idea is to create an array of booleans with a length of the given integer n. Initially, every element will be marked as true, except for 0 and 1, which are not prime.

let primes = [false, false];
for (let i = 2; i < n; i++) {
  primes[i] = true;
}

Now, we can start marking the prime multiples as false. I give all credit for this code to Nic, as this was pretty hard for me to wrap my head around. He creates a limit variable which is the square root of the given integer n. After a lot of thought, I realized that this avoids checking the array for multiples of numbers that are greater than n. For example, if n = 10 we only need to look at the prime numbers less than its square root, which is 3.16. There's no need to look at the multiples of 5 and 7.

let limit = Math.sqrt(n);
for (let i = 2; i < limit; i++) {
  if (primes[i] === true) {
    for (let j = i * i; j < n; j += i) {
      primes[j] = false;
    }
  }
}

Finally, our array is complete and we can simply iterate through it, counting every true instance, returning the final count!

let count = 0;
for (let i = 2; i < primes.length; i++) {
  if (primes[i] === true) {
    count++;
  }
}
return count;

Thanks for following along and I hope this was helpful to someone. I had a lot of fun learning along the way! Again, big thanks to Nic Raboy for his post. See you next week!