素数的快速列举(二)

半年前曾在我的BLOG发过一篇文章(http://blog.csdn.net/northwolves/archive/2005/04/18/351998.aspx),对素数的快速列举进行了初步探讨，随后的讨论在http://community.csdn.net/Expert/topic/4395/4395751.xml?temp=.9719355进行， KiteGirl(小仙妹) 和 jiangsheng(蒋晟.MSMVP2004Jan) 给予了很大的启发，特此将改进后的代码与大家共享。

Sub prime(ByVal n As Long, ByRef prime() As Long)
ReDim prime(5761495) '10^8以内的素数个数
Dim a() As Byte, i As Long, temp As Long, half As Long, p As Long, pcount As Long, mytime As Long, k As Integer
mytime = Timer '计时
half = n \ 2
ReDim a(1 To half)
'the first 10 prime
prime(0) = 2
prime(1) = 3
prime(2) = 5
prime(3) = 7
prime(4) = 11
prime(5) = 13
prime(6) = 17
prime(7) = 19
prime(8) = 23
prime(9) = 29

pcount = 9

p = 3

Do While p * p <= n

temp = p * p

For i = temp To n Step 2 * p 'p的倍数
a(i \ 2) = 1 '设为1表示弃去

Next

again:
p = p + 2

If a(p \ 2) = 1 Then GoTo again

Loop

'把素数分成8种情况：30n+1,30n+7,30n+11,30n+13,30n+17,30n+19,30n+23,30n+29
Dim s(7) As Byte
s(0) = 0
s(1) = 3
s(2) = 5
s(3) = 6
s(4) = 8
s(5) = 9
s(6) = 11
s(7) = 14

For i = 15 To half Step 15

For j = 0 To 7
temp = i + s(j)
If temp > half Then Exit For: Exit For
If a(temp) = 0 Then
pcount = pcount + 1
prime(pcount) = 2 * temp + 1 '赋值
End If
Next

Next
ReDim Preserve prime(pcount) '重设置数组大小节省空间

Debug.Print "n=" & n & ",prime count=" & pcount & ", The calulating time is " & Timer - mytime & " s"
End Sub

Private Sub Command1_Click()
Dim p() As Long
Dim i As Long
For i = 2 To 8
prime 10 ^ i, p
Next
End Sub

返回：

n=100,prime count=25, The calulating time is 0.0000 seconds.
n=1000,prime count=168, The calulating time is 0.0000 seconds.
n=10000,prime count=1229, The calulating time is 0.0000 seconds.
n=100000,prime count=9592, The calulating time is 0.0002 seconds.
n=1000000,prime count=78498, The calulating time is 0.2269 seconds.
n=10000000,prime count=664579, The calulating time is 2.0719 seconds.
n=100000000,prime count=5761455, The calulating time is 15.2344 seconds.

当然，跟C语言的速度还是有一定距离的，但基本上可以满足计算的需要了，编译成EXE文件后还可以更快些。