【ェ】ORANGE pico でエラトステネスの篩

2023年10月29日 12:45

#クリエイターフェス 9日目、テーマは「ェ」である。

エラトステネスの篩

今回は、ORANGE pico でエラトステネスの篩を動かしてみた。
単に動かすだけではなく、実行の様子を可視化するようにした。

アルゴリズム

エラトステネスの篩は、以下の手順 (擬似コード) で指定した数までの非負整数が素数かどうかのテーブルを作成するアルゴリズムである。

n ← 指定した数
isprime ← 0～nの添字が使える配列
isprime[0] ← false
isprime[1] ← false
for i = 2 ... n: // iを2からnまで(両端を含む)1ずつ増やしながらループする
  isprime[i] = true
i ← 2
while i*i <= n:
  j ← i*i
  while j <= n:
    isprime[j] ← false
    j ← j + i
  i ← i + 1

今回の実装では、配列 isprime のかわりにそれぞれの数が素数でないかどうかを表す配列を用い、最初に0に初期化されることを利用して2以降の明示的な初期化を省略した。

プログラム

10 width=10:height=25:cellsize=4:tcolor=rgb(255,255,255):rcolor=rgb(255,255,255):lcolor=rgb(255,255,255)
20 cls:fs$=format$("%%%dd",cellsize):sfs$=format$("%%%dc",cellsize):last=width*height
30 input "ｱﾆﾒｰｼｮﾝ ｶﾝｶｸ [ms] (0:ｼｭﾄﾞｳ) : ",animwait:cursor 0:goto 60
40 if animwait>0 then pause animwait:return
50 if inkey()=0 then goto 50 else return
60 cls:dim notprime(last):notprime(0)=1:notprime(1)=1
70 for i=2 to last
80 gprint (i-1)%width*cellsize*8,(i-1)/width*8,format$(fs$,i),tcolor
90 next
100 gosub 40
110 i=2
120 x=(i-1)%width*cellsize*8:y=(i-1)/width*8
130 line x+8,y,x+cellsize*8-1,y,rcolor:line x+8,y,x+8,y+7,rcolor
140 line x+8,y+7,x+cellsize*8-1,y+7,rcolor:line x+cellsize*8-1,y,x+cellsize*8-1,y+7,rcolor
150 j=i*i
160 notprime(j)=1
170 xj=(j-1)%width*cellsize*8:yj=(j-1)/width*8
180 line xj+8,yj,xj+cellsize*8-1,yj+7,lcolor
190 j=j+i
200 if j<=last goto 160
210 gosub 40
220 gprint x,y,format$(fs$,i),tcolor
230 j=i*i
240 gprint (j-1)%width*cellsize*8,(j-1)/width*8,format$(sfs$,32),tcolor
250 j=j+i
260 if j<=last goto 240
270 gosub 40
280 i=i+1
290 if i*i>last then end
300 if notprime(i) then goto 280
310 goto 120