Prime or not? →
Let’s look at a simple problem if figuring out if a given number is a prime number or not? And how best we can compute it.
A prime number is a whole number greater than 1, that are only divisible by itself and 1.
A naïve approach is to check if the number is divisble by all the numbers starting from 2 to itself. We start from 2
as it is our first prime number.
But, can we do better? Notice that we need to check for numbers only less than or equal to the square root, say sq
of the given number n
to be tested. If there’s a number that divides n
and which is greater than sq
, the result of that division would be a number less than sq
. For example let’s say n = 26
and we want to figure out if n
is prime. We are claiming that we need to check only until the square root of 26
- rounded down to 5
. Let’s pick a number that divides 26
, say 13
and this number on dividing 26
yields 2
. So when we start to check from 2
to 5
, we would have already figured out that it is divisible by 2
and is not a prime. We just ran into another beautiful fact:
there are no even primes greater than 2
That would let us optimize our loop further - if we initially checked whether n
is not 2
, we would check only every other (odd) number to see if it divides.
Primes are beautiful. Hopefully, I will write more posts on them in future.