第10講 Sub プロシージャと Function プロシージャの呼び出し
第６話 素数判定プログラムの改良
実は前回改良した素数判定プログラムはまだ改良の余地があります。
３から対象の整数のルートまですべての奇数で割っていますが、
割るべき数は実は、対象の平方根以下の素数のみでよいのです。
例えば、１６１が素数であるかは、
３，５，７，１１，１３，１７，１９，２３，２９，３１，３７のみで割れなければ素数であると判定してよいのです。
素数判定プログラムでは
３，５，７，９，１１，１３，１５，１７，１９，２１，２３，２５，２７，２９，３１，３３，３５，３７，３９
で割って調べていますからいかに無駄が多いかわかります。
それで判明している素数を蓄えておいてそれで割るようにプログラムを改良しましょう。
Dim sosuu(2000) As Integer
Dim sousuu As Integer
Private Sub CommandButton1_Click()
Dim i As Integer
Dim h As Integer
Dim sousuua As Integer
Dim sousuus As Integer
sousuu = 1
sosuu(sousuu) = 2
Cells(5, 1) = "1から10,000までの素数個数＝"
Cells(6, 1) = 2
For i = 3 To 10000 Step 2
h = sosuuhantei(i)
If h = 1 Then
sousuua = sousuu Mod 20
sousuus = Int(sousuu / 20)
Cells(6 + sousuus, 1 + sousuua) = i
sousuu = sousuu + 1
sosuu(sousuu) = i
Cells(5, 6) = sousuu
End If
Next
End Sub
Function sosuuhantei(g As Integer)
Dim i As Integer, h As Integer, o As Integer
sosuuhantei = 1
o = Int(Sqr(g))
For i = 2 To sousuu
If sosuu(i) > o Then Exit For
If g Mod sosuu(i) = 0 Then
sosuuhantei = 0
Exit For
End If
Next
End Function
このようにして素数判定改良プログラムができます。
