====== エラトステネスの篩  ======


====== 概要  ======

[[https://www.google.co.jp/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0CCMQFjAAahUKEwiq4aiSvN7GAhVIGJQKHduuAsU&url=https%3A%2F%2Fja.wikipedia.org%2Fwiki%2F%25E3%2582%25A8%25E3%2583%25A9%25E3%2583%2588%25E3%2582%25B9%25E3%2583%2586%25E3%2583%258D%25E3%2582%25B9%25E3%2581%25AE%25E7%25AF%25A9&ei=4gSnVaroIsiw0ATb3YqoDA&usg=AFQjCNEXnNhDqT9AzkZZ4NoTzMj9ad8ROw&sig2=7v-nS1E19sNLS1JhCT8v8A&bvm=bv.97949915,d.dGo|エラトステネスの篩]]は、素数を求めるよく知られたアルゴリズムである。

ある数NがN未満の既知の素数のいずれでも割り切れなければその数は素数である。
これを最小の素数である2からはじめて、求めたいNまでくり返していけば、N以下の全ての素数を見つけることが出来る。

====== プログラム  ======

IchigoJamのBASICは16bit符号つき整数しか扱えないのでいずれにしても32,767以下の素数しか処理出来ない。
また、作業に利用可能な配列は[0]～[101]の102個しかないので、単純に実装すると102番目の素数までしか求めることが出来ない。

最もストレートな実装は次のようになるだろう。偶数は素数ではないのは既知なので、[0]=2での除算をはじめから除外している。((FOR I=0 TO N-1ではない理由。))

<code>
10 [0]=2:N=1:T=3
20 F=0
30 FOR I=1 TO N-1
40   IF T%[I]=0 THEN F=1
50 NEXT
60 IF F=0 THEN [N]=T:N=N+1:? "[";N;"]->";T
70 T=T+2
80 IF N<102 THEN GOTO 20
90 END
</code>

求めた素数を保存する必要がなく、ただプログラムとして素数を列記するだけでいいのであれば、Nが素数かどうかの判定は、√N以下の素数についてのみチェックすればいいので、√32,767=181.016573826818以下の素数((即ち41番目の素数である181))までチェックすれば、IchigoJam BASICが扱える全ての整数について、素数かどうかを知ることが出来る。

つまり、作業領域として素数をストックしておく領域は高々41あれば事足りるので、IchigoJam BASICで扱える全ての素数を列挙すること自体は可能である。

このコードは次のようになる。なお、素数2は、ターゲットから偶数を除外―3から開始して、2ずつ増加する、即ち奇数のみ―しているので、自明であることから除外して処理している。

<code>
100 'LIST PRIME NUMBERS
110 CLS:CLT:[0]=3:N=1:T=3:Z=0:C=0
120 I=0
130 C=C+(Z>TICK()):Z=TICK():IF I<102 W=[I] ELSE GOTO 220
140   IF W*W>T GOTO 170
150   IF T%W=0 GOTO 200
160 I=I+1:IF I<N THEN GOTO 130
170 LC 0,0:? "[";N;"]->";T
180 IF N<102 [N]=T
190 N=N+1
200 T=T+2
210 IF T>0 GOTO 120
220 C=C+(Z>TICK()):Z=TICK():LC 0,1:? C*546+Z/60;" Sec"
230 END
</code>

CLTは、TICK()で扱うカウンターをクリアするもので、220行で処理にかかった時間を表示する目的で使っている。

FORループを使っていない理由は、IchigoJam BASICのFOR～NEXTループは、ループを途中で脱出することを許さないためである。
140行目で作業用素数Wが√Tより大きくなった時点((IchigoJam BASICはsqrt()がない（というか実数がない）ので、W*W>Tで両辺をそれぞれ自乗した形で処理している。))で探索を打ち切り、また、150目でいずれかの素数で割り切れた場合に探索を打ち切る場合の両方で、FOR～NEXTからの途中脱出が必要となるので、FOR～NEXTをやめて120～160で、カウンターIとIF文による条件チェックでループを構成している。
このあたりは、原始的なBASIC或いはその直系の祖先となったFORTRANでよく見られるループ構成なので、より「らしい」といえばらしいコーディングではあるが可読性の観点からは決して好ましいとはいえない。

210行目の探索の打ち切り条件が T<0 ((T>0である間は120行へ戻って次の探索を行う。))となっているのは、IchigoJam BASICのオーバーフローを利用した、ややトリッキーな動作である。

本来、打ち切りは T>32767((''IF T<=32767 THEN ...'')) なのだが、Tが32767の時にTに正数nを加算すると、オーバーフローして-32768+n-1になってしまう。
このため、打ち切り条件である T>32767が発生せずに、無限にループしてしまうので、このような処理になっている。
これも古いBASICの処理系ではよく見られた手法なのでらしいといえばらしいのである。
可読性の観点からは決して好ましくないのではあるが。

因みに、最大の素数は3512番目の32749で、この次の素数は32771になる。
なお、最後まで実行した場合、LPC1114ベースのIchigoJamではTICK()が溢れてしまうためCを使って溢れるたびに加算を行い、最後に546をかけて((32768/60=546.1333...))秒数に変換している。なお実行には968秒かかっている。
RISC VベースのIchigoJamで202秒かかった。
従って、RISC Vベースの方が約4.8倍速かった。

[[IchigoJam]]へ戻る