Cryptopgraphy, number theory, algebra, calculus, combinatorics, probability, topology, mother nature, the universe, God, the devil, aliens, the government, the Illuminati, the Freemasons, the Knights Templar, the Vatican. Prime numbers are everywhere. They are the building blocks of all numbers, and they are used in everything from encryption to life itself. But what are they? How do they work? Why are they so important? I have been reading about them for a while now, and I still don’t understand them. I’m not a math person, but lately i’ve been more and more fascinated by it. I wanted to learn more about prime numbers, and how they work. I also wanted to learn about the algorithms used to check if a number is prime, and how they work. So I decided to write this post to help myself understand it better, and maybe help someone else along the way.
Definition of Prime Numbers
Prime numbers are natural numbers greater than 1 that cannot be formed by multiplying two smaller natural numbers.
A natural number is a positive integer, which means it is a whole number greater than zero. 1, 22, 3, 48, 51, etc.
An integer is a whole number i.e 6, -6, 0, 1, 2, 3, etc.
A whole number is a number without fractions or decimals.
- 5 is a whole number
- 5.5 is not a whole number
A prime number is a number that has exactly two distinct positive divisors: 1 and itself.
For example, the number 5 is prime because the only way to multiply two whole numbers to get 5 is 1 x 5. However, the number 6 is not prime because it can be divided by 1, 2, 3, and 6.
The number 1 is not prime because it only has one positive divisor: itself.
The number 2 is prime because it has exactly two distinct positive divisors: 1 and 2. It cannot be written as a product of two smaller natural numbers. 2 is also special, because it is the only even prime number. All other even numbers are divisible by 2, which means they have at least three divisors: 1, 2, and themselves. Since having more than two divisors disqualifies a number from being prime, no even number other than 2 can be prime.
Checking if a number is prime
- We check if the number is less than or equal to 1. If it is, it’s not a prime number — like we established above.
- Then, we check if the number is divisible by 2. If it is, it’s not a prime (unless the number is exactly 2).
- Then, we check if it’s divisible by 3. If it is, it’s not a prime.
- We keep checking divisibility with every number up to number - 1.
For example, to check if 7 is prime:
- 7 is greater than 1 → continue.
- 7 is not divisible by 2 → continue. // 3.5
- 7 is not divisible by 3 → continue. // 2.3333
- 7 is not divisible by 4 → continue. // 1.75
- 7 is not divisible by 5 → continue. // 1.4
- 7 is not divisible by 6 → continue. // 1.1666666666666667
Since none of these divide 7 evenly, 7 is a prime number.
Check if 6 is prime:
- 6 is greater than 1 → continue.
- 6 is divisible by 2 → stop. // 3
- 6 is not prime.
Basically, when checking if a number is prime, you test whether it is divisible by any number between 2 and the number - 1. You exclude 1 and the number itself because a prime number is always divisible by exactly those two, by definition. You’re trying to see if it’s divisible by any other number — if it is, then it’s not prime.
Prime Number Algorithm
Ok, so how do we check if a number is prime in code? The “brute force” way is to check every number from 2 to n - 1, and see if any of them divide n evenly.
function isPrime2(num) {
if (num <= 1) return false; // 1 is not prime
if (num === 2) return true; // 2 is prime
for (let i = 2; i < num; i++) {
if (num % i === 0) return false; // divisible by i - not prime
}
return true;
}If the number is 1 or 2 we do an early return. We then enter a for loop that checks every number from 2 to n - 1. We use the modulus operator to check if the remainder is 0 when dividing num by i. If it is, we return false, because that means it’s not prime. If we get through the whole loop without returning false, we return true, because that means it’s prime.
Since we are checking the condition i < num, we are checking all numbers from 2 to n - 1. This could of course also be written as i <= num - 1.
We could also skip the line if (num === 2) return true;, since we are already checking if num < i in the for loop. Which it is not in the case of 2 (num(2) is not less than i(2)), and thus it will not enter the loop and instead jump to the next line and return true. On the other hand, we could also check if num <= 3 since we know that 3 is also prime. Might be a bit more readable, but any way works.
This is all fine and it works, but it’s not very efficient. Let’s say we want to check if 1,000,000 is prime. We would have to check every number from 2 to 999,999. That’s a lot of checks! The time complexity of this algorithm is O(n), which means it takes linear time to check if a number is prime. This is not very efficient for large numbers.
Luckily we can improve this algorithm by only checking numbers up to the square root of n. This is because if n is divisible by any number greater than its square root, it must also be divisible by a number smaller than its square root. Dont ask me why, im bad at math, and i’ve been trying to understand this without much success. I just have to trust the math nerds on this one.
So what does this look like in practice? Well, say you wanted to check if 25 is prime. The square root of 25 is 5, so you only need to check if it’s divisible by 2, 3, 4, and 5. We can basically skip 20 checks.
And this method becomes much more efficient as the number gets larger. For example, if you wanted to check if 1 Million is prime, you would only need to check divisibility by numbers from 2 up to 1,000, because √1,000,000 = 1,000. That’s just 999 checks instead of 999,998, which is a massive difference.
function isPrime(num) {
if (num <= 1) return false;
for (let i = 2; i <= Math.sqrt(num); i++) {
if (num % i === 0) return false;
}
return true;
}We just check if i is less than or equal to the square root of num instead of num - 1.
Lets try to highlight this with 25, by replacing num with 25 and Math.sqrt(num) with 5.
function isPrime() {
if (25 <= 1) return false;
for (let i = 2; i <= 5; i++) { // 5 is the square root of 25
if (25 % i === 0) return false;
}
return true;
}- 25 is not less than or equal to 1, so we continue.
- We enter the for loop, and
iis 2. iis less than or equal to 5, so we continue.- We check if 25 is divisible by 2. It’s not, so we continue.
iis now 3. We check if 25 is divisible by 3. It’s not, so we continue.iis now 4. We check if 25 is divisible by 4. It’s not, so we continue.iis now 5. We check if 25 is divisible by 5. It is, so we return false.
25 is divisible by a number other than 1 and itself → it is not prime.
Could we improve this even further? Yes, we can skip even numbers altogether since we know that a nunber that is divisible by 2 is not prime.
function isPrime(num) {
if (num <= 1) return false;
if (num <= 3) return true; // 2 and 3 are prime
if (num % 2 === 0) return false; // even numbers are not prime
for (let i = 3; i <= Math.sqrt(num); i += 2) { // check only odd numbers
if (num % i === 0) return false;
}
return true;
}The difference now is that we check if the number is even, and if it is, we return false. We also only check odd numbers in the for loop by incrementing i by 2 instead of 1 and initializing i as 3.
This means we skip all even numbers, which makes the algorithm even faster.
This algorithm has a time complexity of O(√n), which is much more efficient than the previous algorithm. This means it takes square root time to check if a number is prime, which is a significant improvement for large numbers.
Could we improve this eeeeeven more? Why, yes we can! But now we’re getting in to spooky territory. I dont quite understand this one yet, but I will try to explain it anyways.
The 6k ± 1 Rule
The 6k ± 1 rule states that all prime numbers are of the form 6k ± 1, where k is a positive integer. This means that all prime numbers can be expressed as either 6k + 1 or 6k - 1. I know, i’m confused too. I’ll leave this one here for you braniacs to figure out. But just know that this beast right here is an even more efficient way to check if a number is prime.
function isPrime(num) {
if (num <= 1) return false;
if (num <= 3) return true;
// even numbers and multiples of 3 are not prime
if (num % 2 === 0 || num % 3 === 0) return false;
// check only numbers of the form 6k ± 1
for (let i = 5; i <= Math.sqrt(num); i += 6) {
if (num % i === 0 || num % (i + 2) === 0) return false;
}
return true;
}So, what the hell is going on here? Firstly, we’ve added an early return for numbers divisible by 2 or 3. This lets us skip all multiples of 2 and 3 (the smallest primes), which are handled up front.
Why do we need this? Because the loop starts at i = 5 and only checks numbers of the form 6k ± 1 (like 5, 7, 11, 13…). These are the only numbers left that might be prime after we’ve ruled out 2 and 3.
Without the num % 3 === 0 check, we could return the wrong result for smaller numbers. For example: Let’s test if 9 is prime.
- The square root of 9 is 3.
- The loop starts at 5, but 5 > 3, so the loop doesn’t run.
- If we don’t check num % 3 === 0 earlier, the function skips the fact that 9 is divisible by 3, and wrongly returns true.
We then do the
// check only numbers of the form 6k ± 1
for (let i = 5; i <= Math.sqrt(num); i += 6) {
// check i and i + 2
if (num % i === 0 || num % (i + 2) === 0) return false;
}Testing the Algorithms
We have now learned about 4 different algorithms to check if a number is prime.
- The brute force method
- The square root method
- The even number method
- The 6k ± 1 method
Lets put them all to the test and see how they perform by writing a simple test function that runs all 4 algorithms and times them, like so:
function benchmark(fn, label, limit = 100_000) {
const start = performance.now();
for (let i = 2; i < limit; i++) {
fn(i);
}
const end = performance.now();
console.log(`${label}: ${(end - start).toFixed(2)}ms`);
}What this function does is it takes a function, a label, and a limit. It then runs the function for every number from 2 to the limit, and times how long it takes by using the performance API. It then logs the label and the time it took to run the function.
benchmark(isPrimeBrute, "Brute Force");
benchmark(isPrimeSqrt, "Square Root");
benchmark(isPrimeSqrtOptimized, "Even Numbers");
benchmark(isPrime6k, "6k ± 1");Damn computers are fast!! It kind of blows my mind. Just the bruteforce function gets run 100,000 times in less than 500ms 🤯. I mean, i knew computers were fast but this test really made something click for me.
- The square root function was done in 5ms, not surprisingly.
- The optimized even number function was done in 2.7ms.
- The 6k ± 1 function was done in 2ms.
Let’s try it with a limit of 1,000,000 and see how it performs.
benchmark(isPrimeBrute, "Brute Force"); // 43 Seconds!
benchmark(isPrimeSqrt, "Square Root"); // 111ms
benchmark(isPrimeSqrtOptimized, "Even Numbers"); // 47ms
benchmark(isPrime6k, "6k ± 1"); // 30msThis is a massive difference, and it really shows how much more efficient the sqrt algorithms are as we increase the limit.
Lets try it with a limit of 10,000,000 and see how it performs.
benchmark(isPrimeBrute, "Brute Force"); // Nah! Im not doing that.
benchmark(isPrimeSqrt, "Square Root"); // 2144ms
benchmark(isPrimeSqrtOptimized, "Even Numbers"); // 1072ms
benchmark(isPrime6k, "6k ± 1"); // 650msThe pattern is clear. The brute force method is not even worth trying, and the square root method is still pretty fast. The optimized even number method is almost twice as fast (since we are skipping half the numbers), and the 6k ± 1 method is the fastest of them all.
Wrapping Up
I realize that this post is a bit all over the place, and I apologize for that. I just wanted to get my thoughts down on “paper” and try to make sense of it all. I hope this has helped you too, and maybe even inspired you to learn more about them. I’ll leave you wth a quote from a reddit user that I found while researching this topic. I think it sums up the mystery of prime numbers quite well.
That said, […primes are] also interesting because sometimes, they just plain show up in places they don’t seem to ‘belong.’ They have a way of inserting themselves into a problem that you initially thought shouldn’t have ANYTHING to do with prime numbers. But… you can often get knee-deep into some family of questions that have no relevance to primes, on the surface… and somehow find that the answers sort of clump up in nice neat chunks, separated by the ‘fault lines’ of prime numbers. It’s eerie how often that happens.
Kind of like how pi pops up in certain problems that seem to have nothing to do with circles, and it makes you say “What the hell? How did pi get here? There MUST be a circle hiding in this problem, somehow, some way.” Primes similarly just say “Hey, we’re super important, and we get all up in your face when you least expect us,” from time to time.
So, trying to piece together the how’s and why’s of why they seem so damn ubiquitous, is a big reason to try to understand them better. angryWinds on