質問編集履歴
3
エラトステネスの篩の実装を追記しました。
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -157,3 +157,95 @@
|
|
|
157
157
|
###追記
|
|
158
158
|
|
|
159
159
|
具体的には1億以上の数値が入力された場合の演算を高速化したいと考えています。
|
|
160
|
+
|
|
161
|
+
|
|
162
|
+
|
|
163
|
+
###2020/08/25 追記（エラトステネスの篩実装）
|
|
164
|
+
|
|
165
|
+
ご助言頂きましたエラトステネスの篩による実装です。
|
|
166
|
+
|
|
167
|
+
|
|
168
|
+
|
|
169
|
+
```javascript
|
|
170
|
+
|
|
171
|
+
//max_valueにはフォームからの入力値が入ります
|
|
172
|
+
|
|
173
|
+
//ここでmax_valueの値が1億などとされるとこの実装ではmemory outし、ページが停止します。
|
|
174
|
+
|
|
175
|
+
let prime = new Array(max_value).fill(true);
|
|
176
|
+
|
|
177
|
+
|
|
178
|
+
|
|
179
|
+
//primeCounterは本来必要ありませんが、最終的に配列の要素数 = 素数の数としてWebページに出力する都合上、
|
|
180
|
+
|
|
181
|
+
//素数の数をカウントしてその大きさの配列を作る為に使用しています
|
|
182
|
+
|
|
183
|
+
let primeCounter = 0;
|
|
184
|
+
|
|
185
|
+
|
|
186
|
+
|
|
187
|
+
prime[0] = false;
|
|
188
|
+
|
|
189
|
+
prime[1] = false;
|
|
190
|
+
|
|
191
|
+
|
|
192
|
+
|
|
193
|
+
for(let i = 2; i <= maxSqrt; i++) { //maxSqrt には parseInt(Math.sqrt(max_value))+1 が代入されています
|
|
194
|
+
|
|
195
|
+
if(prime[i]) {
|
|
196
|
+
|
|
197
|
+
for(let j = i * 2; j <= max_value; j += i) {
|
|
198
|
+
|
|
199
|
+
cal_counter++; //この変数は別の場所で宣言しており、演算回数を図る為のものです
|
|
200
|
+
|
|
201
|
+
prime[j] = false;
|
|
202
|
+
|
|
203
|
+
}
|
|
204
|
+
|
|
205
|
+
}
|
|
206
|
+
|
|
207
|
+
}
|
|
208
|
+
|
|
209
|
+
for(let i = 0; i < prime.length; i++) {
|
|
210
|
+
|
|
211
|
+
cal_counter++;
|
|
212
|
+
|
|
213
|
+
if(prime[i]) primeCounter++;
|
|
214
|
+
|
|
215
|
+
}
|
|
216
|
+
|
|
217
|
+
|
|
218
|
+
|
|
219
|
+
primeArr = new Array(primeCounter);
|
|
220
|
+
|
|
221
|
+
```
|
|
222
|
+
|
|
223
|
+
|
|
224
|
+
|
|
225
|
+
エラトステネスの篩に関係のない部分は省略しています。
|
|
226
|
+
|
|
227
|
+
エラトステネスの篩というものの解釈がこれであっているのか自信はありませんが、
|
|
228
|
+
|
|
229
|
+
設定された整数と同一の数の配列を宣言し、その中身を一度全て TRUE としておきます。
|
|
230
|
+
|
|
231
|
+
それから 0 と 1 は素数ではないので手動で FALSE を代入します。
|
|
232
|
+
|
|
233
|
+
繰り返しを 2 からスタートし、ネストしたループ処理でその倍数となる要素を全て FALSE にしていきます。
|
|
234
|
+
|
|
235
|
+
ループ処理の際、その要素が既に篩に掛けられ素数ではない判定(FALSE)になっている場合は次へ移行します。
|
|
236
|
+
|
|
237
|
+
この処理を parseInt(Math.sqrt(max_value))+1 以下まで繰り返します。
|
|
238
|
+
|
|
239
|
+
|
|
240
|
+
|
|
241
|
+
最後に配列内で TRUE となっている要素の数を数えればそれが素数の数になっているはず、
|
|
242
|
+
|
|
243
|
+
|
|
244
|
+
|
|
245
|
+
という実装です。
|
|
246
|
+
|
|
247
|
+
|
|
248
|
+
|
|
249
|
+
この実装によって得られた結果は以下の画像の通りです。
|
|
250
|
+
|
|
251
|
+
|
2
初心者アイコンを追加しました。
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -156,4 +156,4 @@
|
|
|
156
156
|
|
|
157
157
|
###追記
|
|
158
158
|
|
|
159
|
-
具体的には1億以上の数値が入力された場合の
|
|
159
|
+
具体的には1億以上の数値が入力された場合の演算を高速化したいと考えています。
|
1
やりたいことの追記をしました。
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -151,3 +151,9 @@
|
|
|
151
151
|
この実装、またはこれ以外のアルゴリズムでより早い計算方法を知りたいです。
|
|
152
152
|
|
|
153
153
|
自分の解法ではこの速度が限界でした。ご鞭撻のほどお願いいたします。
|
|
154
|
+
|
|
155
|
+
|
|
156
|
+
|
|
157
|
+
###追記
|
|
158
|
+
|
|
159
|
+
具体的には1億以上の数値が入力された場合の計算を高速化したいと考えています。
|