VB常用算法（三）素數

1、算法說明

素數（質數）：就是一個大于等于2的整數，并且只能被1和本身整除，而不能被其他整數整除的數。

判別某數m是否是素數的經典算法是：

對于m，從I＝2，3，4，……，m－1依次判別能否被I整除，只要有一個能整除，m就不是素數，否則m是素數。

Private Function sushu(ByVal n As Long) As Boolean

    Dim i As Long

    For i = 2 To n - 1

    If (n Mod i) = 0 Then Exit For

Next I

If I=n then sushu=True

End Function

很顯然，實際上，我們可以改進上面

For i = 2 To n – 1

為：

For i = 2 To int（sqr（m））

這樣可以很好的提高效率。

以上判斷是否為素數的代碼務必識記！

應用舉例

求100－200之內素數。

Private Sub Command1_Click()

    Dim j As Integer

    For j = 100 To 200

        If sushu(j) = True Then

        Print j

        End If

    Next j

End Sub

解題技巧

識記判斷素數的算法過程，根據題意，靈活調用！

實例說明

編程題（2002年春上機試卷04）

         找出10000以內所有可以表示為兩個平方數和的素數。

思路：

首先找10000以內的所有素數，對于每個素數判斷其是否可以表示為兩個平方數之和（即對于任意小于該素數shu的數I，如果I和shu－I均為平方數，則說明其可以表示為兩個平方數之和。）

判斷數I是否為平方數的方法：sqr（i）=int(sqr(i))

Private Sub Command1_Click()

    Dim j As Integer

    Dim m As Long, n As Long

    For j = 2 To 10000

        If sushu(j) = True Then

            If pf(j, m, n) = True Then

                List1.AddItem j & "=" & m & "+" & n

            End If

        End If

    Next j

End Sub

Private Function pf(ByVal shu As Long, m As Long, n As Long) As Boolean

    Dim i As Long

    For i = 1 To shu - 1

        If (Sqr(i) = Int(Sqr(i))) And (Sqr(shu - i) = Int(Sqr(shu - i))) Then

            pf = True

            m = i

            n = shu - i

            Exit Function

        End If

    Next

End Function

2、實戰練習

1)        補充代碼（2002春二（7））

下列程序的功能是：查找四位正整數中的超級素數。超級素數的定義為：當一個素數從低位到高位依次去掉一位數后剩下的數仍然是素數，則此數為超級素數。如數2333、233、23、2均為素數，所以2333為超級素數。

                  Option Explicit

                  Private Sub Command1_Click()

                           Dim I As Integer, flg As Boolean

                     For I = 1001 To 9999 Step 2

                        Call sup_prime(I, flg)

                       If flg Then

                        Debug.Print I

                      End If

                   Next I

                 End Sub

                  Private Sub sup_prime(  （1）  , F As Boolean)

                             Dim p As Integer

                        F = True

                                    Do While N > 0

                                   If prime(N) Then

                                                       （2）

                               Else

                                                 （3）

                                 Exit Sub

                           End If

                      Loop

                  End Sub

                  Public Function prime(p As Integer) As Boolean

                                 Dim k As Integer

                                 If p = 1 Then

                                           Exit Function

                                   Else

                                             For k = 2 To Sqr(p)

                                          If p Mod k = 0 Then Exit Function

                                          Next k

                                              （4）

                          End If

                  End Function

2)        編程題（2004春上機試卷03）

         隨機生成15個兩位正整數，從中找出所有的素數，并記下它是第幾個數，再找出其中最大的素數，并給出它的位置。