Prime Number Routine

[dbrooks74]

Does anyone have an incredibly fast prime number routine? I need to be able to enter a number say 100,000, and it should put into a list box every prime number up to 100,000. We're having a competition so it really has to be crazy fast. Any ideas? Thanks. -db

 

[strongm]

Hit one of the web's search engines, and look for Sieve of Eratosthenes

 

[Jon4747]

Hi,

Private Sub Command1_Click()
Dim num As Integer
Dim num2 As Integer
Dim blnPrime As Boolean
Dim intA As Integer
num2 = InputBox("Number&quot
For num = 1 To num2
blnPrime = True
If num = 1 Or num = 2 Or num = 3 Then
blnPrime = True
ElseIf (num Mod 2 = 0) Then
blnPrime = False
Else
For intA = 3 To num \ 2 Step 2
If (num Mod intA = 0) Then
blnPrime = False
Exit For
End If
Next
End If
If blnPrime = True Then
Debug.Print num & " Is a prime number"
End If
Next
End Sub

Jon

 

[Swi]

If you send me your email address I have a program that gives you a report of all primes in a couple of seconds.

 

[dbrooks74]

You can send it to dbrooks@emh.org

 

[dbrooks74]

Thanks to all the responses. If you have some algorith that really smokes let me know, because were having a competition and it's gotten down to all the primes from 1 to 1,000,000 in 2.5 seconds on a PIII 1.5 Ghz. -db

 

[WilMead]

Jon4747,

Upper limit of the search should be the square root of the number in question.

change [tt]
For intA = 3 To num \ 2 Step 2
[/tt]to[tt]
For intA = 3 To (num ^ .5) Step 2
[/tt]
for greatly improved performance.

The factor pairs occur in pairs around the square root.

Wil Mead
wmead@optonline.net

 

[strongm]

Well, I've written a fairly straighforward Sieve implementation that finds all the primes from 1 to 1000000 in about 450 to 500 milliseconds on an oldish 450MHz PIII when running in the IDE. Does it in approx 100 milliseconds when compiled.
I'll post it if you really don't think that might be considered cheating in the competition...

Note that this timing ignores inserting the primes into a listbox.