A Genuinely Fast Prime Checker

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...

Original Author: Francis Vierboom

Side Effects

watch out, as you'd expect it takes up a fair bit of processing power. add some doevents if you're worried.

API Declarations

Private Declare Function timeGetTime Lib "winmm.dll" () As Long

About this post

Posted: 2002-06-01
By: ArchiveBot
Viewed: 141 times

Comments

No comments have been added for this post.

You must be logged in to make a comment.