回答編集履歴
1
数値のミスを修正
answer
CHANGED
|
@@ -1,5 +1,7 @@
|
|
|
1
|
-
いろいろやってみましたがエラトステネスの篩を分割で処理させる
|
|
1
|
+
いろいろやってみましたがエラトステネスの篩を分割で処理させる
|
|
2
|
+
というコードはうまく実装できませんでした…。
|
|
2
|
-
とりあえず、なんとか計算方法を早くしようとした結果邪道かもしれませんが
|
|
3
|
+
とりあえず、なんとか計算方法を早くしようとした結果邪道かもしれませんが
|
|
4
|
+
次の方法で決着しました（させました…）。
|
|
3
5
|
|
|
4
6
|
### 実装
|
|
5
7
|
|
|
@@ -66,7 +68,6 @@
|
|
|
66
68
|
そのINDEX番号+1が素数の数となる、という計算方法で導き出します。
|
|
67
69
|
当たり前ですが、こと10,000,000以下、または10,000,000付近の答えを導き出す場合は
|
|
68
70
|
エラトステネスの篩より高速です。
|
|
69
|
-
（数値が100,000以下の場合はエラトステネスの篩の方が高速でしたが…）
|
|
70
71
|
|
|
71
72
|
10,000,001以上については試し割り算を行って素数を探していきます。
|
|
72
73
|
その際は、素数表の長さプラスそこからの素数の数となるのでそのように実装しています。
|
|
@@ -90,7 +91,7 @@
|
|
|
90
91
|
|100,000,000|76.98432秒|メモリ不足|**44.97676秒**|5,761,455種類|
|
|
91
92
|
|
|
92
93
|
様々な数値を試してみましたが、素数表を用意した今回の計算方法では、
|
|
93
|
-
10,000,000以下の数値に関してはどのような数値が来ても0.
|
|
94
|
+
10,000,000以下の数値に関してはどのような数値が来ても0.001秒～0.007秒処理が行えるようで、
|
|
94
95
|
素数表に含まれている数値以下であるならおよそ数値の大小関係なくこの速度が出るということでした。
|
|
95
96
|
（検索値以下の最大素数までに何回デクリメントを繰り返すかで処理時間が変化するだけなので検索値の大小で差は生まれにくい）
|
|
96
97
|
|