パソコン活用研究5番街（Visual Basic、Excel(VBA)、BASIC　プログラミング研究）

素数を探す〜エラトステネスの篩い

(準備中）

エラトステネスの篩いの方法で素数を探す方法について。

10000までの素数をエラトステネスの篩いの方法で探してみます。
ただ素数を求めるだけではつまらないので、ついでに素因数分解までしています。

EXCELのB列は素因数分解の途中の数を保存する作業用です。
C列以降に素因数を保存していきます。

10000までの素数を探す場合、10000=100*100なので、100までの素数で素因数分解すればOKです。

�@準備で、A列、B列に1〜10000までの数を記入していきます。

C列が空欄の数値は素数となるので、4以降の自然数を小さい素数（2）から順に素因数分解を
していきます。


Sub prime_fact()
' �@準備
For i = 1 To 10000
Cells(i, 1) = i: Cells(i, 2) = i
Next i

i = 2
While (i < 100)
For j = 4 To 10000

col = 3
While (Cells(j, col) <> "")
col = col + 1
Wend

n = Cells(j, 2)
m = n Mod i


While (m = 0)
n = n / i
Cells(j, 2) = n
Cells(j, col) = i
col = col + 1
m = n Mod i
Wend

Next j

i = i + 1
While (Cells(i, 3) <> "")
i = i + 1
Wend

Wend

End Sub

ABC予想をやってみるでは、エラトステネスの篩いの方法を使わず、
小さい素数（2から）で割り算してみるという力業の方法で素因数分解しています。

る