大したことではないけれど、なんとなく残したくなった。
入門者がやる素数を見つける、生成するプログラムについて。
素数を1000個抽出するとかあるけれど、プログラムを早くしようと思うと素数の性質を理解することになる。
素数は1と自分以外の数字でしか割り切れないわけだが、単純に数字を積み増してひたすら割ることをするのは非効率。その性質にあったプログラムにするとスッキリするし速い。考えていくと「エラストテネスの篩」と同じ考えにたどり着くと思うけれど、それをプログラムにどうやって落とすかになっていく。
まず偶数は2以外は素数じゃないので、対象となる数字は奇数のみ。+2ずつでよい。
一般化しようとすると偶数も対象にすることになるけれど、2は初期値として入れて構わない。というか7くらいまで入れたって構わない。これはすぐに思いつくことだけれども処理が半分になる。
次に割る数は素数だけにする。
素数で割り切れなければその数は素数。なので得られた素数を格納して、その格納した素数を使うというアルゴリズムにすれば、余計な割り算処理が必要なくなる。仮に「3」から順に奇数で割っていくのと比べて、数が大きくなるにつれて処理はずっと少なく済む。HSPでは配列変数を使う。
最後は素数を使う回数。
得られた素数をあるだけ使って割るのは非効率。素数かどうかを判別するだけならを全部の素数を使わなくてもいい。素数でない数は素数の掛け算で表すことができるとも言えるからだ。
例えば「7」を使って割るのは「49」以上からでよい。理由はそれ未満の奇数で7(以上)でしか割れない奇数はないからだ。「21」は「3」で割れるし「35」は「5」で割れる。7^2である「49」から初めて「7」が素数判定で使える。裏を返すと「49」未満の奇数は「3」と「5」で割れなければ全部素数であるということ。
もう少し突っ込むと「9」未満の1以外奇数はすべて素数。「25」未満で「3」で割れない奇数はすべて素数。「121」未満で「3,5,7」で割れない奇数は全て素数。となっていく。「119」は3回割る処理をすれば素数であると判別できる。「119」までの素数全部で割る必要はない。
これらを踏まえてHSPでいうと、ループは三段階になる。
まず素数かどうかを判定するループ。
その判定を受けて素数処理をして、数字を+2するループ。
使う素数の個数とループ回数、および最終的な素数個数を管理するループ。
下のループが上のループを含む形になる。
これをうちのwin8.1のA10-7850のHSP3.32だかは100万個の素数を出すのに100秒弱かかる。実数で処理すると300秒くらいかかる。何故かは知らんけど。アルゴリズムがシンプルなので、言語やCPUで分かりやすく性能差が出そうな気がする。ベンチとかにいいかも。
これをさらに速くするアルゴリズムとかどうやればいいのかわからない。
対象の数字が大きくなるほど判定に使われる素数の個数は増えていく。それだけ判定に時間がかかる。1000万個出すとしたら数時間かかるんじゃないだろうか。スパコンで100秒だとどのくらいの素数を計算できるんだろう。
