首页>软件水平考试教程>文章详情

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

3/18/2007
25190

  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


  解题技巧

  识记判断素数的算法过程,根据题意,灵活调用!

  实例说明

  编程题

  找出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) 补充代码

  下列程序的功能是:查找四位正整数中的超级素数。超级素数的定义为:当一个素数从低位到高位依次去掉一位数后剩下的数仍然是素数,则此数为超级素数。如数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