Optimally determine if a number is prime

When you are asked to determine if a number is prime or not through a piece of code, in your head, you are already thinking of two things:

1. What is a prime number?
2. How would I code it up?

I’d imagine most of you would get to the solution pre-ttt-y easily.

How are you addressing the two questions above?

1. Oh, a prime number is a number that does not have any divisors, except 1 and the number itself. Fair.
2. Brute force it. In a loop, starting from 2, because 1 is a divisor for every number, let’s run the loop till n-1 (n being the number in question )to determine if each of the numbers is a divisor of n. If not, then n is a prime number. Else, if we have a number x in [2,n-1] that divides the number n perfectly, then n is not a prime number.

Brute force method to iterate through numbers 2 to n — 1.

Okay, that looks okay. Straight forward. However, the pressing question after every solution is:

Can you optimise it?

Hmm.

Optimisation

Do we really need to check for all the numbers from 2 to n-1?
If a number n is not a prime number, then there should be two numbers x, y such that x * y = n.

For that to be true, x and y both should be in the range of 1 to √n, that is, x < √n and y < √n, otherwise if x > √n and y > √n, we’ll have (x * y) > (√n * √n). Which then means, (x * y) > n.

So we can simply check if there is a number x that it is in the range [2,√n] such that n is divisible by x.

Optimised code where the for loop runs from 2 to sqrt(n).

While we are dealing with computers of ridiculous speeds and optimisations of such kinds is probably not what is being chased but I wouldn’t put it past any interviewer to ask you this. :) They usually ask you stuff that, in every day life, seems obvious and of which the mechanism is never really given importance.

Thank you if you got till here! .. and just like that, I have my first medium post delivered.