IsPrime Function

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?

Share the Post:
Share on facebook
Share on twitter
Share on linkedin

Overview

The Latest

microsoft careers

Top Careers at Microsoft

Microsoft has gained its position as one of the top companies in the world, and Microsoft careers are flourishing. This multinational company is efficiently developing popular software and computers with other consumer electronics. It is a dream come true for so many people to acquire a high paid, high-prestige job

your company's audio

4 Areas of Your Company Where Your Audio Really Matters

Your company probably relies on audio more than you realize. Whether you’re creating a spoken text message to a colleague or giving a speech, you want your audio to shine. Otherwise, you could cause avoidable friction points and potentially hurt your brand reputation. For example, let’s say you create a

chrome os developer mode

How to Turn on Chrome OS Developer Mode

Google’s Chrome OS is a popular operating system that is widely used on Chromebooks and other devices. While it is designed to be simple and user-friendly, there are times when users may want to access additional features and functionality. One way to do this is by turning on Chrome OS