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

文章作者 100test 发表时间 2007:06:14 11:56:05
来源 100Test.Com百考试题网

　　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

src="/ncre2/js/wxgg.js">