エラトステネスの篩

差分

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

この比較画面へのリンク

--- エラトステネスの篩 [2015/07/16 04:51] – 外部編集 127.0.0.1
+++ エラトステネスの篩 [2022/01/06 09:31] (現在) – [プログラム] araki
@@ 行 32: / 行 32: @@
 つまり、作業領域として素数をストックしておく領域は高々41あれば事足りるので、IchigoJam BASICで扱える全ての素数を列挙すること自体は可能である。
-このコードは次のようになる。
+このコードは次のようになる。なお、素数2は、ターゲットから偶数を除外―3から開始して、2ずつ増加する、即ち奇数のみ―しているので、自明であることから除外して処理している。
 <code>
 'LIST PRIME NUMBERS
-CLT:[0]=2:N=1:T=3
+ CLS:CLT:[0]=3:N=1:T=3:Z=0:C=0
-I=1
+I=0
-IF I<102 THEN W=[I] ELSE END
+ C=C+(Z>TICK()):Z=TICK():IF I<102 W=[I] ELSE GOTO 220
-   IF W*W>T THEN GOTO 170
+   IF W*W>T GOTO 170
-   IF T%W=0 THEN GOTO 200
+   IF T%W=0 GOTO 200
 I=I+1:IF I<N THEN GOTO 130
- LOCATE 0,0:? "[";N;"]->";T
+ LC 0,0:? "[";N;"]->";T
-IF N<102 THEN [N]=T ELSE END
+IF N<102 [N]=T
 N=N+1
 T=T+2
-IF T>0 THEN GOTO 120
+IF T>0 GOTO 120
- LOCATE 0,0:? TICK()/60;" Sec"
+ C=C+(Z>TICK()):Z=TICK():LC 0,1:? C*546+Z/60;" Sec"
 END
 </code>
@@ 行 59: / 行 59: @@
 行目の探索の打ち切り条件が T<0 ((T>0である間は120行へ戻って次の探索を行う。))となっているのは、IchigoJam BASICのオーバーフローを利用した、ややトリッキーな動作である。
-本来、打ち切りは T>32767((IF T<=32767 THEN ...)) なのだが、Tが32767の時にTに正数nを加算すると、オーバーフローして-32768+n-1になってしまう。
+本来、打ち切りは 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]]へ戻る

エラトステネスの篩.1437022263.txt.gz · 最終更新: 2015/07/16 04:51 by 127.0.0.1