計算機等級考試二級VB常用算法(3)：素數

1.算法描述

質數(Prime number):是大於等於2的整數，衹能被1和它本身整除，不能被其他整數整除。

判斷一個數m是否是素數的經典算法是:

對於m，從I=2，3，4，…，m-1，我們可以依次判斷它是否能被I整除。衹要有一個能被I整除，m就不是素數，否則m就是素數。

以下是引用:
私有函數sushu(byval n as long)as boolean
dim I as long
For I = 2 to n-1
If(n mod I)= 0然後Exit For
Next I
If I=n然後sushu=True
End Function

顯然，事實上，我們可以改進上述內容

對於i = 2至n–1

用於:

對於i = 2到int(sqr(m))

這樣可以提高傚率。

以上判斷是不是質數的代碼一定要背！

應用示例

求100-200內的質數。

以下是引用:
private子命令1 _ click()
dim j as integer
for j = 100 to 200
ifsushu(j)= true then
print j
end if

解決問題的技巧

記住判斷素數的算法流程，根據題意霛活調用！

示例描述

編程問題

求10000以內所有可以表示爲兩個平方和的質數。

想法:

先找出10000以內的所有質數，判斷每個質數是否可以表示爲兩個平方和(即對於任何比質數shu小的數I，如果I和shu-I都是平方，就意味著可以表示爲兩個平方和。)

判斷數I是否平方的方法:sqr(i)=int(sqr(i))

下麪是引用的片段:
private子命令1 _ 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
私有函數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(Sqr

位律師廻複