winzip icon

A Genuinely Fast Prime Checker

Email
Submitted on: 1/19/2015 4:10:00 AM
By: Francis Vierboom (from psc cd)  
Level: Intermediate
User Rating: By 5 Users
Compatibility: VB 5.0, VB 6.0
Views: 2325
 
     This program is faster than any prime checker I've seen here. 2 main reasons 1)this only checks for factors up to the square root of the number, not half the number like most programs. 2)it only checks for prime factors. (number theory 101 - all factors are primes or products of primes. no point in checking to see if 12's a factor if you've already checked 2 or 3.)

obviously this means 'training' the program so it knows lots of primes. recommended: before you get started, use the 'find primes' up to 100000 (40 sec on a p200). this will dramatically speed up all prime checks up to 10^10. if you train it up to 1000000 (3min 24sec) then it will be much faster all the way up to 10^12.

the program holds all the prime numbers that have been found so far in both an array and a file, so after a while it begins to eat memory. i haven't reallly tested that; its a warning just in case though.

the best i've seen is a checker that decided 1000000000000091 was a prime in 5 min and 5 sec (Mike Frey at http://www.planet-source-code.com/xq/ASP/txtCodeId.7168/lngWId.1/qx/vb/scripts/ShowCode.htm). This one does it in 21.1 seconds (having trained it up to 4.6 million). I'm sure theres still some tweaking to do though...

 

Windows API/Global Declarations:

Can't Copy and Paste this?
Click here for a copy-and-paste friendly version of this code!
'**************************************
'Windows API/Global Declarations for :A Genuinely Fast Prime Checker
'**************************************
Private Declare Function timeGetTime Lib "winmm.dll" () As Long
winzip iconDownload code

Note: Due to the size or complexity of this submission, the author has submitted it as a .zip file to shorten your download time. Afterdownloading it, you will need a program like Winzip to decompress it.Virus note:All files are scanned once-a-day by Planet Source Code for viruses, but new viruses come out every day, so no prevention program can catch 100% of them. For your own safety, please:
  1. Re-scan downloaded files using your personal virus checker before using it.
  2. NEVER, EVER run compiled files (.exe's, .ocx's, .dll's etc.)--only run source code.
  3. Scan the source code with Minnow's Project Scanner

If you don't have a virus scanner, you can get one at many places on the net including:McAfee.com


Report Bad Submission
Use this form to tell us if this entry should be deleted (i.e contains no code, is a virus, etc.).
This submission should be removed because:

Your Vote

What do you think of this code (in the Intermediate category)?
(The code with your highest vote will win this month's coding contest!)
Excellent  Good  Average  Below Average  Poor (See voting log ...)
 

Other User Comments


 There are no comments on this submission.
 

Add Your Feedback
Your feedback will be posted below and an email sent to the author. Please remember that the author was kind enough to share this with you, so any criticisms must be stated politely, or they will be deleted. (For feedback not related to this particular code, please click here instead.)
 

To post feedback, first please login.