Prime numbers
James Robb ・4 min read
Algorithms (7 Part Series)
In this article we will be writing an algorithm to check if a provided number is a prime number or not. Before we begin let's define a few phrases that will be used during this article:
- Factor: a number or quantity that when multiplied with another produces a given number or expression
- A prime number: A whole number that only has two factors which are itself and one
- A composite number: A whole number which is not prime
We can also state the following statements about primes and composites:
- The numbers
0
and1
are neither prime nor composite - All even numbers are divisible by two and so all even numbers greater than two are composite numbers
- All numbers that end in five are divisible by five therefore all numbers that end with five and are greater than five are composite numbers
With that all said, let's start working on our tests and the implementation.
Tests
describe("prime number tests", () => {
it('ignores negative numbers', () => {
expect(isPrime(-1)).toBe(false);
});
it('ignores floating point numbers', () => {
expect(isPrime(1.0001)).toBe(false);
});
it('ignores 0 and 1', () => {
expect(isPrime(0)).toBe(false);
expect(isPrime(1)).toBe(false);
});
it('identifies primes as expected', () => {
const primes = [2, 3, 5, 7, 11, 13, 17, 19];
for (const prime of primes) {
expect(isPrime(prime)).toBe(true);
}
});
it('identifies non-primes as expected', () => {
const composites = [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20];
for (const composite of composites) {
expect(isPrime(composite)).toBe(false);
}
});
});
The tests here are quite simple but still covers our bases. We begin by testing that negative numbers, floating point numbers, 0 and 1 aren't prime. From there we test the numbers from 2 through 20 to check that the primes in that range come back as true
and the composites come back as false
. This makes sure we stick rigidly to the definition of what a prime number is and verify it by checking those numbers in the arbitrary range of 2 through 20.
Implementation
/**
* @function isPrime
* @description A function to identify if a given number is prime
* @param {Number} number - The number to check
* @returns {Boolean} represents if the provided number is prime or not
*/
function isPrime(number) {
if(Number.isInteger(number) === false) return false;
if(number <= 1) return false;
if(number % 2 === 0 && number > 2) return false;
const square = Math.sqrt(number);
for (let divisor = 3; divisor <= square; divisor += 2) {
if (number % divisor === 0) return false;
}
return true;
}
We begin the implementation of our isPrime
function by filtering floating point numbers, numbers less than or equal to 1 and numbers divisible by 2 which are greater than 2 itself since 2 is prime. This helps us return false
fast for items we know are not prime before running the inner loop and wasting any cycles.
From there we get the square root of the provided number. Lets illustrate the maths behind this to understand why we choose to do this.
If a number n
is not a prime, it can be factored into two factors a
and b
.
n = a * b
If both a
and b
were greater than the square root of n
then a
times b
would be greater than n
. As such, at least one of those factors must be less than or equal to the square root of n
. If we can't find any factors less than or equal to the square root, n
must be prime.
Therefore we only need to loop up to the square root of the given number
to check if the number
is prime or not.
We start our loop at 3 since 2 is prime and will return true
anyway due to the initial checks we run at the start of the function body. For each iteration of the loop we check if the provided number
is fully divisible by the current divisor
and if it is, we know the number
cannot be prime since it must be a multiple of the divisor
. In which case, we return false
since a prime number should only be a multiple of itself and 1.
On each iteration we add 2 to the
divisor
as you may have noticed. This is because we know we aren’t dealing with an even number due to our previous checks and odd numbers aren’t divisible by even ones without a remainder being present and so we know we can skip checking even numbers during the iteration process. — thanks the @lukaszahradnik for the suggestion to do it like this
If no divisors between 3 and the square root of number
were found then the number must be prime and so we return true
.
Conclusions
There are many important real world use cases for prime numbers. Cicadas time their life cycles by them, modern screens use them for controlling the colour intensity of pixels and let's not forget the fact that they make up the very basis of computational security in implementations such as the RSA (Rivest–Shamir–Adleman) cryptosystem.
At the time of writing this article, the largest known prime to date is 2^{82,589,933}-1 (2 to the power of 82,589,933 minus 1). The resulting prime number is 24,862,048 digits long and that would make it approximately 2.5 times the length of the longest known book written to date in terms of digit count compared to character count using the average word length of 5 to determine the aforementioned character count.
Overall primes can be a fun topic to explore and have many important uses, there is even an organisation committed to finding more primes. I hope you learned something with this article and we will be exploring more mathematical constructs in the future and I hope to see you there!
Algorithms (7 Part Series)
Easy improvement would be skipping even numbers
You make a good point, I hadn’t considered that actually!
If I was to add this change it would just replace the conditional at the beginning of the function body which checks if the number is even and greater than 2 so this shouldn’t ever execute unless it’s an odd number that is passed in as input, in which case this becomes a good performance improvement, especially for larger numbers since odd numbers aren’t divisible by even ones without a remainder being present of course.
Thanks for commenting! 👍
It doesn't replace the conditional which checks if the number is even. That condition is still important.
Prime numbers are not even (except 2), so we don't have to check if they are divisible by even number.
Exactly, if you check the article, I added as much to the implementation section and tagged you with the kudos 😉
Nice! Thanks for tagging, it wasn't really needed. I just wanted to improve solution.
I always give credit where credits due so all good and thanks again for the comment 🙂👍.