エラトステネスの篩

差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

--- エラトステネスの篩 [2022/01/06 11:25] – [プログラム] araki
+++ エラトステネスの篩 [2022/01/06 18:31] (現在) – [プログラム] araki
@@ 行 32: / 行 32: @@
 つまり、作業領域として素数をストックしておく領域は高々41あれば事足りるので、IchigoJam BASICで扱える全ての素数を列挙すること自体は可能である。
-このコードは次のようになる。
+このコードは次のようになる。なお、素数2は、ターゲットから偶数を除外―3から開始して、2ずつ増加する、即ち奇数のみ―しているので、自明であることから除外して処理している。
 <code>
 'LIST PRIME NUMBERS
-CLS:CLT:[0]=2:N=1:T=3
+CLS:CLT:[0]=3:N=1:T=3:Z=0:C=0
 I=0
-IF I<102 W=[I] ELSE GOTO 220
+ C=C+(Z>TICK()):Z=TICK():IF I<102 W=[I] ELSE GOTO 220
    IF W*W>T GOTO 170
    IF T%W=0 GOTO 200
@@ 行 47: / 行 47: @@
 T=T+2
 IF T>0 GOTO 120
-LC 0,1:? TICK()/60;" Sec"
+ C=C+(Z>TICK()):Z=TICK():LC 0,1:? C*546+Z/60;" Sec"
 END
 </code>
@@ 行 63: / 行 63: @@
 これも古いBASICの処理系ではよく見られた手法なのでらしいといえばらしいのである。
 可読性の観点からは決して好ましくないのではあるが。
+因みに、最大の素数は3512番目の32749で、この次の素数は32771になる。
+なお、最後まで実行した場合、LPC1114ベースのIchigoJamではTICK()が溢れてしまうためCを使って溢れるたびに加算を行い、最後に546をかけて((32768/60=546.1333...))秒数に変換している。なお実行には968秒かかっている。
+RISC VベースのIchigoJamで202秒かかった。
+従って、RISC Vベースの方が約4.8倍速かった。
 [[IchigoJam]]へ戻る

エラトステネスの篩.1641435900.txt.gz · 最終更新: 2022/01/06 11:25 by araki