计算机等级考试二级VB常用算法:素数

2007-5-16 16:01:34   Count:
    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

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

浏览该文章的用户为您推荐了该信息: 
       
   
   
 
站内检索:
本月授课安排
栏目导航
阅读排行