The Prime Number Test : A Brute Force Approach
Q: How to check if a given integer is a prime or not?
This was another question I was asked during a tech interview and at the time I remember trying to find a feasible solution that would be efficient as well.
The solution I came up with had its flaws in terms of efficiency. The approach at the time was to do some initial testing for numbers equal to or less than 3 and greater than or equal to -1 as primes.
The next step I was to test for numbers between 3 and half of the number. The idea was that there would a smaller factor less or equal to half if the number is not prime.
I refined the code from the interview keeping the original idea. (See below)
The problem with this code is the run-time. Even though it is a brute-force method, the time complexity in this case is O(n). It is definitely a solution but not an effective one. For instance, let’s consider a large prime, say 179426549, it takes about 6.69 seconds to check if it is a prime.
So after the interview, I spend some time thinking about how to increase the efficiency of the brute force method and remembered the primality test for Skiena’s book “The Algorithm Design Manual” where it talked about doing a brute force factor search till the square root of the number.
This would definitely improve the algorithm as it doesn’t go through significantly a small amount of factors. It still uses the same idea of the small factor being less than the square root of the number instead of half the number.
Here’s the code for the same.
Note that the time complexity in this case is O(√n). For instance, let’s consider a large prime, say 179426549, it takes about 0.0036 seconds to check if it is a prime and that is significantly better than the 6.69 seconds from earlier.
There are more efficient methods available to check if a number is prime, especially when we are checking for a significantly large primes used in cryptography. I’ll be looking into some other algorithms out there like Fermat’s Little Theorem and Miller-Rabin in the next part of this series of Primality Tests.
