Find the prime numbers in a given array using Vanilla JS - Beginner Friendly

I came across this task while going through the documentation on MDN, and thought to blog about it in a beginner friendly way. I am in that space where I realize that if I cannot possibly explain my code to someone else, I probably haven't understood it as well as I would like to think. So here we go, with the most elemental explanation. As I have included in the title, this post might be most suited for those who are beginners or new to Vanilla Javascript.

What are prime numbers?

Prime numbers are natural numbers that are greater than one AND only have two positive divisors - 1 and the number itself. In other words, a prime number cannot be formed by multiplying two numbers.

NB: Natural numbers refer to positive integers that begin from 1 and continue all the way. For this reason, decimals and fractions are NOT natural numbers.

2 is a prime number. Why? because you cannot get 2 by multiplying any other number except 1 and itself (1 X 2).

3 is also a prime number for the same reason.

4 is NOT a prime number, and that's because its divisors are 1, 2 and 4 - (1 x 4), (2 X 2).

5 is a prime number.

6 is NOT a prime number because it has the following divisors. (1 X 6), (2 X 3)

7 is a prime number

90 is NOT a prime number, but 97 is... and so on and so forth.

You might also have noticed, from the pattern, that prime numbers are ALL odd numbers with the exception of 2. The simple reason for this is that if a number is even, ie it is divisible by 2, then that means it has more than 2 divisors: 1, 2 and the number itself. Automatically, that means it is not a prime number.We can check for this using the modulo % operator in Javascript. This operator, also known as the Remainder always returns the remainder after division.

Let's take 4%2 for example. 4/2 gives us 2 and remainder 0.

So 4%2 returns 0

13%4 will return 1.

That's because 13/4 gives us 3 remainder 1.

Another way to look at it is, if we divide a given number by 2, and have no remainder, then that is an even number, and therefore cannot be a prime number.

Pseudo-code to get the prime numbers in a given array

Using this as a basis to check for our prime numbers, let's create a function called checkPrime() with the following in mind:

• a Prime number is only divisible by 1 and itself.

• if a number is less than or equal to 1 it is NOT a prime number and should return false. Check our definition of a prime number above. 1 is not a prime number because it can only be divided by one number - itself!

• 2 is a prime number because it is only divisible by 1 and 2

• if a number is an even number, that cannot be a prime number

For the purposes of this example, I am using an array with a random set of numbers, creating a function that takes in a parameter, num to check if it is less than or equal to 1, if it is equivalent to two, if it is an even number, and if none of these applies, to return true.

I then call the filter method on the array provided. Since the filter method creates a new array with elements that pass a given test, in this case, the findPrime function. This however, does not quite work as expected because when we check what it logs to the console, we find 9 listed there, and yet 9 is NOT a prime number because we can get it using - (3 X 3)

const array = [-3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13];

const findPrime = (num) => {
    if (num <= 1) {
        return false;
    }

    if (num === 2) {
        return true;
    }

    if (num % 2 === 0) {
        return false;
    }

    return true;
};

console.log(array.filter(findPrime));

//[2, 3, 5, 7, 9, 11, 13]

Using a for loop to eliminate odd numbers that are NOT prime numbers

To get around this, we need to find a way to check if the parameter is divisible by other factors - and not necessarily 2 for even numbers. An easy way to get this done is to use a for loop. The loop allows us to divide the given number by a unique number in each iteration. I got this idea from Marina's post on Medium. Here's the code, Let's take 3 as an example from the array we used:

const findPrime = (num) => {
    //3 is def more than 1 so proceed to the next lines of code
    if (num <= 1) {
        return false;
    }

    //3 is not strictly equal to 2 so proceed
    if (num === 2) {
        return true;
    }

    //in the first loop, i=2 and num=3, 2<3 so the code in the loop runs. 3%2 is NOT equal to 0, so we iterate again.
    //in the second loop, i = 3, 3 is NOT less than 3, so the loop breaks and cannot return 'false', so the code continues to the end where it returns true, meaning that 3 is a prime number.
    for (let i = 2; i < num; i++) {
        if (num % i === 0) {
            return false;
        }
    }

    return true;
};

If at any point, the remainder is 0 within the loop, the function exits at this point and returns false (meaning since that number is divisible by another number, it cannot be a prime number). If, on the other hand, there is a remainder, the loop continues iterating until this condition is met i<num.

Refactoring the code to cater for large numbers

While this works, it can be cumbersome for bigger numbers as that would create numerous iterations. This is where the use of square roots comes in.

The idea behind using square roots in prime number checks is that you only need to check divisors up to the square root of the number you are testing. This is because if a number has a divisor greater than its square root, it must also have a corresponding divisor smaller than its square root.

So for say, 100, it has a square root of 10. (10 X 10), but it also has other divisors such as (2 X 50), (4 X 25), (5 X 20). To put into perspective the last paragraph, if a number (100) has a divisor (20) greater than its square root (10), then its corresponding divisor will be smaller than its square root (5).

This means that we only need to check for divisors up to the square root of the number to cover its possible divisor pairs. If no divisor is found within this range, then there will not be a divisor greater than the square root.

In the refactored code, we initialize the loop first, and then check that i is less than or equal to the square root of the number, and then increment i. This is notably different from the previous code where we checked the number as is. We use the <= sign so that it is inclusive of the square root itself as a potential divisor. This prevents the loop from breaking before reaching the square root itself.

Let's take 64 for instance. The square root of 64 is 8. so if we set i < Math.sqrt(num), the loop breaks when i gets to 7, because when i=8 8 is NOT less than 8. Here's the code to illustrate this:

const array = [
    -3, -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 81, 199,
];

const findPrime = (num) => {
    if (num <= 1) {
        return false;
    }

    if (num === 2) {
        return true;
    }

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

    return true;
};

console.log(array.filter(findPrime));
//[2, 3, 5, 7, 11, 13, 199]

Prime numbers have practical applications in daily life, ranging from computer algorithms, to netowrk routing and cryptography among others.

I really hope this is helpful for anyone who is just getting their feet wet with Javascript.

Happy coding!