素数さがし

再び教育っぽいネタ。いわゆる「エラトステネスのふるい」で素数を探すプログラムです。

• 実行すると、画面に「1234567890123…」と数字が表示されます。1行目が1〜30、2行目が31〜60、3行目が61〜90…と30ごとに1の位の数を表示しています。最後は690までです。
• エラトステネスのふるいを始めます。まず1は素数ではないので消します。次に2を残して2の倍数を消します。次に3を残して3の倍数を消します。次に5を残して5の倍数を消します。…と、残っている数の最小のものを残して、その倍数を消す作業を、690の半分・345までくり返します。
• 消されずに残った数が素数です。画面がビューモードになって、カーソルが左上の「2」で点滅します。矢印キーでカーソルを上下左右の素数に移動できます。カーソル位置の実際の数は、画面左下に表示されます。

素数探し（ふるい分け）はIchigoJamが10数秒でやってくれます。今は素数探索をコンピュータ計算で行っているので、その一端を知るにはいいんじゃないでしょうか。
また、690までの範囲でどんな素数があるか、見てみるとなかなか興味深いです。
例えば素数が出てくる間隔は、「数が大きくなるに連れて広がっていくんじゃないか？」と思いますが、実際はそうでもありません。この範囲で一番間隔が広いのは523と541で18差。その後でも、569と571、641と643など、隣り合う奇数が素数の所がいくつかあります。
この「素数の分布・規則性」は、100万ドルの賞金がかかった数学の難問「リーマン予想」につながる問題で、長年研究されていますがまだ解明されていません。

プログラムリストはこちら。

10 'Sosuu:Sieve of Eratosthenes
20 CLV:CLS
30 FOR C=0 TO 9:FOR B=0 TO 7
40 A=C*8+B
50 POKE #780+A,~PEEK(#180+A)
60 NEXT:NEXT
70 FOR I=0 TO 660 STEP 30
80 FOR J=1 TO 30
90 ?J%10;
100 NEXT
110 ?
120 NEXT
130 LC 0,0:?"*";
140 S=2
150 '@SLOOP
160 LC 0,23:?S;"ﾉ ﾊﾞｲｽｳ";
170 M=1
180 '@NLOOP
190 M=M+1:N=S*M
200 IF N>690 GOTO 230
210 GSB 510:LC X,Y:?"*";
220 GOTO 180
230 '@NEND
240 GSB 530
250 IF S<346 GOTO 150
260 LC 0,23:?"           ";
270 N=2
280 '@VLOOP
290 V=0:GSB 580
300 IF BTN(LEFT) GSB 390
310 IF BTN(RIGHT) GSB 460
320 IF BTN(UP) GSB 370
330 IF BTN(DOWN) GSB 440
340 V=1:GSB 580
350 WAIT 10
360 GOTO 280
370 '@NUP
380 N=N-29
390 '@NLEFT
400 N=N-1:IF N<1 N=N+690
410 GSB 510
420 IF SCR(X,Y)=42 GOTO 390
430 RTN
440 '@NDOWN
450 N=N+29
460 '@NRIGHT
470 N=N+1:IF N>690 N=N-690
480 GSB 510
490 IF SCR(X,Y)=42 GOTO 460
500 RTN
510 '@XY
520 X=(N-1)%30:Y=(N-1)/30:RTN
530 '@SNEXT
540 S=S+1:IF S>345 RTN
550 N=S:GSB 510
560 IF SCR(X,Y)!=42 RTN
570 GOTO 530
580 '@VSUB
590 GSB 510
600 LC X,Y:?CHR$(48+V*192+N%10)
610 LC 0,23:?N;"  ";
620 RTN

MixJuiceでもダウンロードできます。
?"MJ GET comich.net/ichigojam/sosuu.txt"

※なお、実際は最大数690の平方根、√690≒26の倍数までふるいにかければ、作業は終了です。

250 IF S<346 GOTO 150

540 S=S+1:IF S>345 RTN

を、

250 IF S<27 GOTO 150

540 S=S+1:IF S>26 RTN

に変えれば、26の倍数までになります。
今回はわかりやすく半分の345までにしました。
計算時間はあまり変わりません。