Breaking Down DSAs: Count Primes
Tags: algorithms, javascript, programming, learning
Published: 2019-08-11 21:00:45

---
title: Breaking Down DSAs: Count Primes
published: true
description: 
tags: algorithms, javascript, programming, learning
---

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](https://leetcode.com/explore/interview/card/top-interview-questions-easy/) that I've been working through, and it's called [count primes](https://leetcode.com/problems/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](https://www.w3schools.com/js/js_arithmetic.asp) 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.

```javascript
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:

```javascript
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](https://en.wikipedia.org/wiki/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](https://www.thepolyglotdeveloper.com/2015/04/determine-if-a-number-is-prime-using-javascript/) 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.

```javascript
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.

```javascript
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!

```javascript
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](https://www.nraboy.com/) for his post. See you next week!