计算机等级考试二级VB常用算法(3)：素数

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

希望与更多计算机等级考试的网友交流，请进入计算机等级考试论坛

更多信息请访问：考试吧计算机等级考试栏目