Prime numbers

Posted by Tamsin on August 01, 2001 7:02 AM

Does anyone know how a quick way of outputting all of the prime numbers upto a specified number? I've used this macro which although effective, is fairly crude and slows dramatically for say 10000.

Sub GetPrimes()
'Finds all prime numbers up to 1000
Dim lCur As Long
Dim lToDivide As Long
Dim bIsPrime As Boolean
Dim t As Single
Dim rowCounter As Long
t = Timer
rowCounter = 1
For lCur = 3 To 10000
bIsPrime = True
For ldivide = 2 To lCur
If ldivide &LT;&GT; lCur And lCur Mod ldivide = 0 Then bIsPrime = False: Exit For 'Not prime
Next ldivide
If bIsPrime Then Cells(rowCounter, 1) = lCur: rowCounter = rowCounter + 1
Next lCur
MsgBox Timer - t
End Sub

Thanks,
Tamsin.

Posted by Damon Ostrander on August 01, 2001 8:10 AM

Tamsin,

I have a VBA demo that I have used for teaching VBA that implements the Eratosthenes Sieve algorithm for finding primes. If you would like me to send it to you just email me. If nothing else I think you will find it interesting because it uses some simple graphics to display what the algorithm is doing while it is running.

Damon

Posted by Ivan F Moala on August 02, 2001 12:49 AM

Try this change to your code;
Tests I did show times of .35 sec Vs 12.5 secs

Sub GetPrimesV2()
'Finds all prime numbers up to 10000
Dim lCur As Long
Dim lToDivide As Long
Dim bIsPrime As Boolean
Dim t As Single
Dim rowCounter As Long

t = Timer
rowCounter = 1
Application.ScreenUpdating = False
For lCur = 3 To 10000
If IsPrime(lCur) Then Cells(rowCounter, 1) = lCur: rowCounter = rowCounter + 1
Next lCur
Application.ScreenUpdating = True
MsgBox Timer - t
End Sub

Private Function IsPrime(ByVal lngNumber As Long) As Boolean
'By Joe Bourne
Dim lngTop As Long 'The highest number to check
Dim i As Long

Select Case lngNumber
Case 1
IsPrime = False 'NOT a Prime number
Exit Function
Case 2, 3 'Add some more here If you really think it will help!!
IsPrime = True 'chuck out some known primes
Exit Function
Case Else
'//// chuck out even numbers as being Not Prime

If lngNumber Mod 2 = 0 Then
IsPrime = False 'Not Prime
Exit Function
End If
End Select

i = 3 'Fixed 27/03/01

If (lngNumber Mod i) = 0 Then
IsPrime = False 'Number is Not prime
Exit Function 'Bail out
Else
'Move the highest number to check down to avoid pointelss checks
lngTop = (lngNumber \ i) 'Integer divide For speed.
End If
i = i + 2 'Move To the Next odd number
Loop While i &LT;= lngTop 'Not sure we need the "=" here.

'If we make it to this point then the number is prime.
IsPrime = True 'Number is prime
End Function

Ivan