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

会计考友 · 发表于 2012-7-31 22:15:04

　　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

会计考友 · 发表于 2012-7-31 22:15:05

</p>　　
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个两位正整数，从中找出所有的素数，并记下它是第几个数，再找出其中最大的素数，并给出它的位置。

		自动登录	找回密码
密码			立即注册

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

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

浏览过的版块