An algorithm a day : How to check for a prime number in JavaScript
It is nearly guaranteed that at some time in your coding education you will be asked to write some type of function that involves prime numbers. It is a popular exercise in coding boot camps and sometimes even pop up in job interviews.
What are prime numbers?
A prime number is a natural number greater than 1 whose only factors are 1 and the number itself. That is, it can only be divided equally by 1 and itself.
Natural numbers are positive integers such as 1, 5, 201, 229999 etc. The number 0, fractions, decimals, and negative numbers are not natural numbers.
The number 5 is a prime number because its ONLY factors are 1 and 5. There is no other way to ‘create’ the number 5.
The number 4 is not a prime number because 2 x 2 also gives us 4.
The number 20 is not a prime number because 5 x 4 also gives us 20, as well as 2 x 10.
Prime numbers are never even (except for 2)
One of the quickest ways to check if a number is a prime number or not is to check if it is an even number. If a number can be divided by 2 without leaving a remainder it no longer meets the definition for a prime number — a number that can only be divided equally by 1 and itself.
In JavaScript we can check for even numbers by using the modulo operator (%).
The modulo operator returns the remainder after one integer is divided by another.
For example 12 % 5 returns 2.
And 59 % 5 returns 4.
If you divide an integer by 2 and the remainder is 0, we know that the integer is an even number.
For example 10 % 2 = 0
And 2200 % 2 = 0
in JavaScript it will look something like this:
num % 2 === 0
So let’s start creating our JavaScript function to check if a number is a prime number or not:
function isPrime(num) {
if (num % 2 === 0) { return false;
} return true;}
//isPrime(40) gives us a False answer
//isPrime(101) gives us a True answer
Remember that 2 IS a prime number
The function above will however also state that 2 is not a prime number, so we will need to rewrite our function. We can also take care of any other integers that are not whole numbers such as 0 and negative numbers.
function isPrime(num) {
if (num === 2) return true;
if (num <= 1) return false; if (num % 2 === 0) {
return false;
}
return true;
}//isPrime(0.5) gives us a False answer
//isPrime(2) gives us a True answer
//isPrime(577) gives us a True answer
The keyword ‘return’ signals an exit of the function when it encounters a statement that is true. If the number is 2, the function stops running at the second line:
if (num === 2) return true;You can find a large list of known prime numbers here to help you check the function.
Not all uneven numbers are prime numbers
This function works okay for checking if a number is even or not but fails with uneven numbers such as 9 and 27 that are not prime numbers.
We are going to have to check if the parameter can be divided into other factors (except for 1, itself and 2) without leaving a remainder. The number 9 for example can also be divided by 3.
We do this by making use of a for loop where at every iteration, the parameter is divided by another loop variable. The loop keeps running until there are no remainders or there are no more loop variables available.
function isPrime(num) {
if (num <= 1) return false;
if (num === 2) return true; for (let i= 2; i < num; i++) { //we start with 2 to weed out the even numbers if (num % i === 0) {
return false;
}
} return true;
}//isPrime(9) is False
//isPrime(11) is True
//isPrime(27) is False
The function keeps looping and checking for remainders. At every iteration, the argument is divided by a new loop variable and the remainder is checked. If the remainder is 0, it means the argument is completely divisible by another number other than itself and is not a prime number.
Side note: What is the difference between a parameter and an argument?
Parameters are the variables used as a part of the function definition. For example the num in function isPrime(num) is the parameter.Arguments are the values passed to the function when it is invoked. For example
the number 9 in isPrime(9) is the argument.
If there is a remainder, the function iterates again until it reaches the limit at
i < numWhen the final iteration is reached and there is still a remainder left, the argument is a prime number and the function stops.
We end with a loop variable that is one number smaller than the parameter because we are not interested in factors that are larger than the argument.
A quick demonstration
Let’s demonstrate this with the prime number of 5.
function isPrime(num) {
if (num <= 1) return false;
//5 is larger than 1, so we continue with the function if (num === 2) return true;
//5 is not 2, so we continue with the function for (let i= 2; i < num; i++) {
if (num % i === 0) {
return false;
}
}
return true;}
First loop:
1. i = 2 and 2 < 5, so we continue with the loop
2. 5 % 2 gives a remainder so we do not exit the loop but continue with i++
Second loop:
1. i = 3 and 3 < 5, so we continue with the loop
2. 5 % 3 gives a remainder so we do not exit the loop but continue with i++
Third loop:
1. i = 4 and 4 < 5, and we have reached the end of the loop because 5 is not < than 5
2. 5 % 4 gives a remainder. This means that the number 5 is a prime number
Using square roots with larger prime numbers
Prime numbers quickly escalate into huge numbers. This means that our for loop keeps on iterating from the one loop variable to the next for numerous times.
We can shorten the process by using the square root of a parameter. A square root of an integer is the number that was multiplied by itself to create a product.
The square root of 81 is 9 because 9 x 9 = 81.
Instead of iterating from 2 to 80 to check if there are any remainders left or not, we can just iterate up to and including 9, the square root of 81.
9 % 9 = 0, which means that 81 is not a prime number.
This makes sense because 9 x 9 are factors of 81 which means that it doesn’t comply with the definition of a prime number — a number that can only be divided equally by itself and 1.
In JavaScript, you can find the square root of a number by using Math.square. We write it like this:
Math.sqrt(num);Let’s use it in our function that checks if a number is a prime number:
function isPrime(num) {
if (num <= 1) return false;
if (num=== 2) return true; let num2 = Math.sqrt(num);//num2 is the square root of num for (let i= 2; i <= num2; i++) { //note that we are working now with the square root if (num2 % i === 0) { return false;
}
}
return true; }isPrime(521) //is True
isPrime(9801) //is False
isPrime(13037) //is True
Why are prime numbers so useful?
In Contact, the science fiction book by Carl Sagan, aliens send a long string of prime numbers as proof that their message is from an intelligent life force. We are not (yet) communicating with extraterrestrials via prime numbers but use them in various ways right here on planet Earth.
Cicadas emerge in sync in exact prime number cycles. The irregular cycles means that no predators have evolved to live off these insects. Also, the fact that they all emerge from the ground at time increases an individual’s chance of survival.
Screens use prime numbers to define color intensities of pixels. They are also used in tool manufacture to get rid of harmonies. Two gears that share a multiple will engage the same teeth over and over again which leads to an uneven wear pattern. Gears that have a prime number of teeth on their cogs will last longer.
Prime numbers are however mostly in modern computer security. It is not that difficult to find large prime numbers but it is very difficult to factor large numbers into prime numbers.
It is easy to figure out that 27 is 3 x 3 x 3 but it is much more difficult to find that 2,244,354 is 2 x 3 x 7 x 53,437. And 2,244,354 is not even that large a number. Finding the prime factors is technically a matter of time but because it will take so long we say that it cannot be done.
Modern encryption algorithms use the fact that there is no computer yet that can take a super-large number and quickly figure out which primes went into making it.
You may be shopping online or sending an encrypted message via an app on your phone but somewhere, somehow prime numbers are helping you to keep your secrets safe.
Here are three more links to other “An algorithm a day” articles:
