江苏省高校计算机等级考试命题研究院 江苏省高校计算机等级考试辅导
二级VB常用算法(三)素数

VB常用算法(三)素数

                    曹苏群  http://caosuqun.bokee.com                  

1、算法说明

素数(质数):就是一个大于等于2的整数,并且只能被1和本身整除,而不能被其他整数整除的数。

判别某数m是否是素数的经典算法是:

对于m,从I234……m1依次判别能否被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 intsqrm))

这样可以很好的提高效率。

以上判断是否为素数的代码务必识记!

 

应用举例

100200之内素数。

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,如果IshuI均为平方数,则说明其可以表示为两个平方数之和。)

判断数I是否为平方数的方法:sqri=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))

下列程序的功能是:查找四位正整数中的超级素数。超级素数的定义为:当一个素数从低位到高位依次去掉一位数后剩下的数仍然是素数,则此数为超级素数。如数2333233232均为素数,所以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个两位正整数,从中找出所有的素数,并记下它是第几个数,再找出其中最大的素数,并给出它的位置。