Prime numbers macro

... studying and implementing a Sieve of Eratosthenes type algorithm. Allegedly, this is a more efficient algorithm. http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

I like the "allegedly" bit.

The referenced Wikipedia article gives what the writer claims is "An optimized implementation" of Eratosthenes' sieve.

Just for interest, I tried translating that "optimized implementation" to VBA. The VBA code is given below. And yes, it does run quite fast.

But contrary to what is claimed, it doesn't seem to be particularly optimal for at least a couple of reasons.
1. The writer's Booleans are all initially set to be true. The default VBA Boolean is false, so an extra (but unnecessary) VBA loop is needed to set them as true. Unnecessary loops can be inefficient, and this is so in this case.
2. A number of the non-primes are sieved out more than once. Arithmetical redundancy of that sort takes up calculation resources and time and isn't optimal.

Probably the writer was well aware of these, but felt the need to keep his/her Wikipedia exposition as straightforward as reasonable.

However, it's not that hard to give an alternate version of the code below to run about 30-40% faster. Maybe even faster again with a better code-writer than I.

Sub wikipedia_primes_translated()

Const n& = 10 ^ 7   'all primes less than 10 million to be listed
Dim b(2 To n) As Boolean, a#(), i&, j&, c&
ReDim a(1 To n / (Log(n) - 2), 1 To 1)

For i = 2 To n: b(i) = True: Next i

For i = 2 To Int(n ^ 0.5)
    If b(i) Then
        For j = i ^ 2 To n Step i
            b(j) = False
        Next j
    End If
Next i

For i = 2 To n
    If b(i) Then c = c + 1: a(c, 1) = i
Next i

Cells(3).Resize(c) = a

End Sub

Incidentally, using a division/remainder approach (rather than the step approach) to the Sieve of Erathosthenes is very inefficient.

Originally Posted by kalak

I like the "allegedly" bit.

The referenced Wikipedia article gives what the writer claims is "An optimized implementation" of Eratosthenes' sieve.

Just for interest, I tried translating that "optimized implementation" to VBA. The VBA code is given below. And yes, it does run quite fast.

But contrary to what is claimed, it doesn't seem to be particularly optimal for at least a couple of reasons.
1. The writer's Booleans are all initially set to be true. The default VBA Boolean is false, so an extra (but unnecessary) VBA loop is needed to set them as true. Unnecessary loops can be inefficient, and this is so in this case.
2. A number of the non-primes are sieved out more than once. Arithmetical redundancy of that sort takes up calculation resources and time and isn't optimal.

Probably the writer was well aware of these, but felt the need to keep his/her Wikipedia exposition as straightforward as reasonable.

However, it's not that hard to give an alternate version of the code below to run about 30-40% faster. Maybe even faster again with a better code-writer than I.

Sub wikipedia_primes_translated()

Const n& = 10 ^ 7   'all primes less than 10 million to be listed
Dim b(2 To n) As Boolean, a#(), i&, j&, c&
ReDim a(1 To n / (Log(n) - 2), 1 To 1)

For i = 2 To n: b(i) = True: Next i

For i = 2 To Int(n ^ 0.5)
    If b(i) Then
        For j = i ^ 2 To n Step i
            b(j) = False
        Next j
    End If
Next i

For i = 2 To n
    If b(i) Then c = c + 1: a(c, 1) = i
Next i

Cells(3).Resize(c) = a

End Sub

Incidentally, using a division/remainder approach (rather than the step approach) to the Sieve of Erathosthenes is very inefficient.

Amazing code! I only list prime by Bitwise Sieve method as following code.

Sub is_prime2()

Dim n As Long
Dim i As Long
Dim r As Long
Dim p As Long
Dim start As Double

Application.ScreenUpdating = False
Application.Calculation = xlCalculationManual

Range("B:B").Clear
n = Application.InputBox("Input prime range", "Input prompt", 1, Type:=1)
Range("B1") = "1 to " & n

start = Timer
r = 2
Cells(2, 2) = 2

For i = 2 To n
    p = 2
    Do While Cells(p, 2) <= i ^ 0.5
       If i Mod Cells(p, 2) = 0 Then GoTo np
        p = p + 1
    Loop
    Cells(r, 2) = i
    r = r + 1
np:
Next

Range("F2") = Timer - start

Application.ScreenUpdating = True
Application.Calculation = xlCalculationAutomatic