Everybody knows how to check if a number is prime:

1) Set a divisor to two;

2) “Mod” the number by the divisor;

3) If the result is zero, then we have our answer: It is not prime;

4) If it is something different from zero, then increment the divisor;

5a) If the divisor is equals to the number being tested, then we got our answer: It is prime;

5b) If it is not, then start over at step 2.

The problem is when you have a long number, like 961,748,927 – it can take a while to process it.

Sure, we can optimize the algorithm above by avoiding to set the divisor to an even number, because we already know the tested number is not even. But even so, we probably will be wasting some processor’s cycles.

We can reduce the number of iterations by stopping at the number’s square root. If the square root times square root does not yield our number, there’s no sense in incrementing the divisor.

For instance, 961,748,927’s square root is 31,012.0771…, so let’s stop at 31,012.

961,748,927 divided by 31,012 is 31,012.1542… and “Modded” by 31,012 is 4,783. As it is not zero, it should be prime.

If we would increment the divisor to 31,013, dividing our number by it would result in something lower than the previous result of 31,012.1542… But we can be sure that this lower number still does not divide evenly the number being tested, because we already tried it. We are incrementing the divisor starting from 2 all the way to 31,012, right?