計算機等級考試二級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ù)的代碼務(wù)必識記!
    應(yīng)用舉例
    求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)用!
    實例說明
    編程題
    找出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