Login | Register   
LinkedIn
Google+
Twitter
RSS Feed
Download our iPhone app
TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK
Browse DevX
Sign up for e-mail newsletters from DevX


Tip of the Day
Language: Visual Basic Classic (6 and earlier)
Expertise: Advanced
Oct 11, 2016

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?

Oracy
 
Comment and Contribute

 

 

 

 

 


(Maximum characters: 1200). You have 1200 characters left.

 

 

Sitemap
Thanks for your registration, follow us on our social networks to keep up-to-date