エラトステネスの篩は、素数を求めるよく知られたアルゴリズムである。

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

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

最もストレートな実装は次のようになるだろう。偶数は素数ではないのは既知なので、[0]=2での除算をはじめから除外している。¹⁾

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

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

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

このコードは次のようになる。

100 'LIST PRIME NUMBERS
110 CLS:CLT:[0]=2:N=1:T=3
120 I=0
130 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 LC 0,1:? TICK()/60;" Sec"
230 END

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

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

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

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

IchigoJamへ戻る