計算機等級考試二級VB常用算法(3)：素數(shù)

1、算法說明

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

判別某數(shù)m是否是素數(shù)的經(jīng)典算法是：

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

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））

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

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

應用舉例

求100－200之內(nèi)素數(shù)。

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

解題技巧

識記判斷素數(shù)的算法過程，根據(jù)題意，靈活調(diào)用！

實例說明

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

         找出10000以內(nèi)所有可以表示為兩個平方數(shù)和的素數(shù)。

思路：

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

判斷數(shù)I是否為平方數(shù)的方法：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

希望與更多計算機等級考試的網(wǎng)友交流，請進入計算機等級考試論壇

更多信息請訪問：考試吧計算機等級考試欄目