素数的快速列举

好久没来这里了。最近看了一些数论方面的文章，受益匪浅。想到我们初学VB时，利用循环查找素数是必修之课，随手写了两段列举素数的代码，并详细注释。自己感觉还是比较快的。 代码如下：

'*******************************************************************************
'  Target:to get all prime numbers smaller than a certain number      

'    Author：northwolves                                                                            

'   Reference："Sieve of Eratosthenes"                                                    

 '   Createdate：2005-04-18 00:00:00                                                   

'*******************************************************************************

Sub showprime1(ByVal max As Long) 'find all prime numbers smaller than max(max>=3)

Dim p() As Long, i As Long, j As Long, number As Long, sqrtmax As Long, beprime As Boolean 'difinations

number = 1
ReDim p(1 To number)
p(1) = 2 ' the unique even prime number
Debug.Print p(1) 'show the first prime number

If max < 3 Then Exit Sub 'since we want do something

For i = 3 To max Step 2 ' skip those even number
     sqrtmax = Int(Sqr(i)) + 1 'get the largest non-self factor  of i
     beprime = True ' init
  For j = 1 To number ' try all primer numbers we have found before.
      If i Mod p(j) = 0 Then beprime = False: Exit For 'not a prime number
      If p(j) > sqrtmax Then Exit For 'unless we'll waste our time
  Next
 
  If beprime = True Then ' then it is a prime number
      number = number + 1 'add to it's count
      ReDim Preserve p(1 To number) 'define again
      p(number) = i
      Debug.Print i ' output the prime number
  End If

Next
Debug.Print "There are " & number & " prime numbers below " & max ' show some message

End Sub
Private Sub Command1_Click() ' show all prime numbers smaller than 100000
showprime1 100000
End Sub

'************************************************************************
'   Target:to get the first n prime numbers from 2,3,....       

'    Author：northwolves                                                   

'    Reference："Sieve of Eratosthenes"                             

'   Createdate：2005-04-18 00:00:00                               

'************************************************************************

Sub showprime2(ByVal n As Long) ' get the first n(n>1) prime numbers

Dim p() As Long, i As Long, j As Long, number As Long, sqrtmax As Long, beprime As Boolean

number = 1
ReDim p(1 To number)
p(1) = 2 ' the unique even prime number
Debug.Print 2 'show the first prime number

If n < 2 Then Exit Sub 'since we want do something
i = 3
Do While number <= n
       sqrtmax = Int(Sqr(i)) + 1 'get the largest non-self factor  of max
       beprime = True ' init
    For j = 1 To number ' try all primer numbers we have found before.
   
        If i Mod p(j) = 0 Then beprime = False: Exit For 'not a prime number
        If p(j) > sqrtmax Then Exit For 'unless we'll waste our time
       
    Next
   
    If beprime = True Then ' then it is a prime number
        number = number + 1 'add to it's count
        ReDim Preserve p(1 To number) 'define again
        p(number) = i
        Debug.Print i ' output the prime number
    End If
i = i + 2 ' skip those even number
Loop

Debug.Print "The " & n & " prime Number Is " & p(number); "" ' show some message

End Sub

Private Sub Command2_Click() ' show the first 1000 prime numbers
showprime2 1000
End Sub