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