エラトステネスの篩
差分
このページの2つのバージョン間の差分を表示します。
次のリビジョン | 前のリビジョン | ||
エラトステネスの篩 [2015/07/16 04:51] – 外部編集 127.0.0.1 | エラトステネスの篩 [2022/01/06 09:31] (現在) – [プログラム] araki | ||
---|---|---|---|
行 32: | 行 32: | ||
つまり、作業領域として素数をストックしておく領域は高々41あれば事足りるので、IchigoJam BASICで扱える全ての素数を列挙すること自体は可能である。 | つまり、作業領域として素数をストックしておく領域は高々41あれば事足りるので、IchigoJam BASICで扱える全ての素数を列挙すること自体は可能である。 | ||
- | このコードは次のようになる。 | + | このコードは次のようになる。なお、素数2は、ターゲットから偶数を除外―3から開始して、2ずつ増加する、即ち奇数のみ―しているので、自明であることから除外して処理している。 |
< | < | ||
100 'LIST PRIME NUMBERS | 100 'LIST PRIME NUMBERS | ||
- | 110 CLT:[0]=2:N=1:T=3 | + | 110 CLS:CLT:[0]=3:N=1:T=3:Z=0:C=0 |
- | 120 I=1 | + | 120 I=0 |
- | 130 IF I< | + | 130 C=C+(Z> |
- | 140 IF W*W> | + | 140 IF W*W>T GOTO 170 |
- | 150 IF T%W=0 THEN GOTO 200 | + | 150 IF T%W=0 GOTO 200 |
160 I=I+1:IF I<N THEN GOTO 130 | 160 I=I+1:IF I<N THEN GOTO 130 | ||
- | 170 LOCATE | + | 170 LC 0,0:? " |
- | 180 IF N< | + | 180 IF N<102 [N]=T |
190 N=N+1 | 190 N=N+1 | ||
200 T=T+2 | 200 T=T+2 | ||
- | 210 IF T> | + | 210 IF T>0 GOTO 120 |
- | 220 LOCATE 0,0:? TICK()/ | + | 220 C=C+(Z> |
230 END | 230 END | ||
</ | </ | ||
行 59: | 行 59: | ||
210行目の探索の打ち切り条件が T<0 ((T> | 210行目の探索の打ち切り条件が T<0 ((T> | ||
- | 本来、打ち切りは T> | + | 本来、打ち切りは T> |
このため、打ち切り条件である T> | このため、打ち切り条件である T> | ||
これも古いBASICの処理系ではよく見られた手法なのでらしいといえばらしいのである。 | これも古いBASICの処理系ではよく見られた手法なのでらしいといえばらしいのである。 | ||
可読性の観点からは決して好ましくないのではあるが。 | 可読性の観点からは決して好ましくないのではあるが。 | ||
+ | |||
+ | 因みに、最大の素数は3512番目の32749で、この次の素数は32771になる。 | ||
+ | なお、最後まで実行した場合、LPC1114ベースのIchigoJamではTICK()が溢れてしまうためCを使って溢れるたびに加算を行い、最後に546をかけて((32768/ | ||
+ | RISC VベースのIchigoJamで202秒かかった。 | ||
+ | 従って、RISC Vベースの方が約4.8倍速かった。 | ||
[[IchigoJam]]へ戻る | [[IchigoJam]]へ戻る | ||
エラトステネスの篩.1437022263.txt.gz · 最終更新: 2015/07/16 04:51 by 127.0.0.1