Algorithms 101: Count Primes in JavaScript

Noob v. Algorithms #17, the Sieve of Eratosthenes

picture from algolist.net

Before we get started on today’s challenge, a word about prime numbers: They are, of course, numbers that are greater than one that are divisible only by themselves and one.

If you’re like me, you probably learned about them many times by the time you graduated from high school. But you missed the memo on why we care. The short answer is, we can use very large prime numbers for encryption. More details on that here.

For today’s puzzle in LeetCode:

There are several ways to solve this, but having heard about the Sieve of Eratosthenes, I wanted to try his way!

Dude was a librarian, mathematician, athlete …

Eratosthenes (pronounced air-uh-TOSS-thuh-neez), a Greek mathemetician, philosopher, historian, librarian, athlete, poet and inventor, was born in 276 BC.

He’s best known for calculating the circumference of the earth based on his observations that at the same time of day, sunlight fell at different angles in different towns.

He’s credited with coining the word ‘geography’; and his buds in Alexandria, Egypt nicknamed him Pentathlos (an athelete who completes in five different events).

The Sieve of Eratosthenes

He invented an elegant algorithm for finding all primes between 1 and any given number. Let’s use 120 as an example.

  1. First, write down all the numbers between 1 and 120.

You can see how it works below in this gif from wikimedia.com:

from wikimedia.com

Notice: each time we find a number n that has not been crossed out, the first multiple of that number that has not already been crossed out is n*n.

Once we find an n where n*n is greater than the lat number in our list, there’s no point in continuing.

So how does this work in code?

Step 1. Write down all the numbers up to n.

Let’s try n = 10. Remember, we are looking for a count of prime numbers less than 10, so we’ll stop at 9.

We can do this using JavaScript’s keys() method. From the documentation: The keys() method returns a new Array Iterator object that contains the keys for each index in the array.

let nums = [...Array(n).keys()]
=> [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

You might wonder, why are we starting with zero, when we really want to start with 2? In the next step, we want to iterate over these numbers, and we want the index we are iterating over to equal the value at that index.

Step 2. Starting with the number 2, cross out all subsequent multiples of 2.

In code, instead of crossing the numbers out, we can change their values. To make it easier to see what’s going on, when we cross out a number, let’s change it’s value to the string “nope” — as in, nope, that number was not a prime.

let n = 10
let nums = [...Array(n).keys()]
=> [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
for(let i = 2; i*i < n; i++){
if(nums[i] !== "nope"){
for(let j = i*i; j < n; j += i){
nums[j] = "nope"
}
}
}

Let’s unpack that. In our for loop:

let i =2;

Usually, when we iterate over an array, we want to iterate over the whole array, starting with index 0. In this case, we want to start with the number 2, which is at index 2.

i*i < n;

When we find a number n where n*n is greater than the last number in our array, we won’t have any number to cross out. So we can stop our loop there.

Crossing out numbers

if(nums[i] !== “nope”)

Remember, we decided to ‘cross out’ numbers by changing their values to “nope”. In the above line, we look at nums[i] to see if it not crossed out. If it’s not crossed out, we continue.

for(let j = i*i; j < n; j += i){
nums[j] = "nope"
}

Looking at the code above, let’s say i = 2. We set a new iterator j with an initial value of i*i, or 4. The first time through this loop we ‘cross out’ the element at nums[j] (4) to “nope”. Then we increment j by 2, cross that number out by changing it to “nope”. We repeat until we run out of numbers in the array.

So while i = 2, after the first time through the loop, our nums array looks like this:

After the second time:

After the third time:

The next time we increment j, it equals 10, which is beyond the scope of our loop. So we move on to the next i loop, where i=3. We set j to an initial value of (9) and cross that number out.

Next, the j loop tells us to cross out all subsequent multiples of three … but the next multiple, 12, is not in our array, so move back to the i loop, where the next number that’s already crossed out is 5. Then we go back to the j loop and try to cross out i*i (25), but that’s not in our array.

Back to our i loop, we reach i=7, and we try to cross out i*i, but again, there’s no 49 in our loop. So we’ve reached the end.

Step 3. Turn our altered nums array into a list of primes

So now we need to change this:

into this:

[2,3,5,7]

To do that, we can iterate over nums, and grab every element that’s greater than 1:

for(let i = 0; i < nums.length; i++) {
if(nums[i] > 1){
primes.push(nums[i])
}
}

Step 4. Return the length of the array.

The directions tell us to return the number of primes between 1 and n, not the actual primes. We can use JavaScript’s .length():

return primes.length()

All together now:

Let’s speed it up a bit!

According to LeetCode, the above code runs takes over 200ms to run, which is pretty slow.

We can speed that up by changing the way we cross things out. Instead of changing their values to a string, we can change them to the number 1:

And now, we’re faster than most!

Play with this code

You can play with the code here on repl.it: https://repl.it/@Joan_IndianaInd/count-primesjs

You can also visualize the code as it executes here, with Pythontutor.org.

Copyright © Joan Indiana Lyness 2019

In case you missed it: Algorithms 101 #16, Find Pairs in JavaScript

Next: Algorithms 101 #18, Group Anagrams in JavaScript

JavaScript in Plain English

Learn the web's most important programming language.

Joan Indiana Lyness

Written by

Full-stack developer, Ruby, Rails, JavaScript, i love! React. My portfolio: https://joan-indiana-lyness.com/projects

JavaScript in Plain English

Learn the web's most important programming language.

More From Medium

More from JavaScript in Plain English

More from JavaScript in Plain English

More from JavaScript in Plain English

5 Secret features of JSON.stringify()

More from JavaScript in Plain English

More from JavaScript in Plain English

7 really good reasons not to use TypeScript

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade