ひたすら、素数を数えあげていただけのプログラムを進化させて、3DSの処理速度を少し分かりやすく(？)したようなプログラムになりました。 五桁の素数が出てくるまで10分弱掛かりました。

私は25秒で5桁の素数を発見しました(ドヤッ ※勿論旧3DSです

す…すごい！ やっぱり、全ての整数をその数から1ずつ引いていった数で割っているから、時間がかかるな…

素数か否か調べる対象の数から偶数を除外したら、5分程度になりました！

さらに、割る数から偶数を除いたら、約2分半

48フレームで5桁の1007までの素数を求めることができました。旧3DSです。

まさかの、1秒未満！？

人知を越えたお

どんどん最適化されて行く………

n=2^20-1=1048575 以下の素数の個数を表示します。 new3dsで290frames程度。 「エラトステネス」のふるいというアルゴリズムです。

10 行めの ' を消すと、1048575 以下の全ての素数を表示します。

配列 p[] には n 未満の全ての奇素数が入っているので、奇数 x (x>=3) が素数かどうか調べるには (1)x<n の場合、p[i]<=xの範囲で (1a) p[i]==x となる p[i] が存在すれば x は素数 (1b) そうでなければ x は合成数 (2)x>=mの場合、 p[i]<=sqr(x)の範囲で (2a) x mod p[i] == 0 となる p[i] が存在すれば x は合成数 (2b) そうでなければ x は素数 となります。

みきさん改めMIKIさんのを旧3DSで実行したら1055～1065フレーム（4回実行）でした。 さらに、1048576個も要素取れるんなら T[(I-3)>>1] とか T[(K-3)>>1] とかケチケチしないで T[I], T[K] でいいだろ、と変えると、991～1001フレーム（4回実行）と少しだけ速くなりました。

お題に合わせてちろっといじって、人のふんどし（はしたない。失礼！）で相撲をとってみたところ……旧3DSで8フレームでした。 まさに宇宙人知外。