  Advertiser Disclosure
 TODAY'S HEADLINES  |   ARTICLE ARCHIVE  |   FORUMS  |   TIP BANK Specialized Dev Zones Research Center eBook Library .NET Java C++ Web Dev Architecture Database Security Open Source Enterprise Mobile Special Reports 10-Minute Solutions DevXtra Blogs Slideshow     Home » Tip Bank » Visual Basic
Language: Visual Basic Classic (6 and earlier)
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 Submit a Tip Browse "Visual Basic" Tips Browse All Tips   Thanks for your registration, follow us on our social networks to keep up-to-date