回答編集履歴
6
ikadzuchiさんからの引用
answer
CHANGED
|
@@ -63,7 +63,8 @@
|
|
|
63
63
|
質問者のhnk_llさんはおそらく，
|
|
64
64
|
「if文で条件を絞って，エラトステネスの篩を実装しよう」
|
|
65
65
|
と思ったのかもしれません．
|
|
66
|
-
しかし，この**if文の条件文が計算量の多い計算を含んでいるので，すごい時間がかかっているのです．
|
|
66
|
+
しかし，この**if文の条件文が計算量の多い計算を含んでいるので，すごい時間がかかっている**のです．
|
|
67
|
+
ikadzuchiさんのおっしゃるとおり，除算や剰余はたいへん遅い処理なのです…
|
|
67
68
|
|
|
68
69
|
## 解説2：どのように改善すればよいか
|
|
69
70
|
|
5
見出しを付けた
answer
CHANGED
|
@@ -1,3 +1,5 @@
|
|
|
1
|
+
## 結論
|
|
2
|
+
|
|
1
3
|
hnk_llさんのソースコードが以下の通りですね．
|
|
2
4
|
|
|
3
5
|
```c
|
|
@@ -43,6 +45,7 @@
|
|
|
43
45
|
|
|
44
46
|
にすると，大分速くなると思います．
|
|
45
47
|
|
|
48
|
+
## 解説1：なぜ従来の手法が遅いのか
|
|
46
49
|
従来の手法ですと，
|
|
47
50
|
```c
|
|
48
51
|
for (j = i + 1; j < 246913; j++)
|
|
@@ -57,15 +60,25 @@
|
|
|
57
60
|
|
|
58
61
|
この画像は従来の手法でした場合のfor文の中で回っている部分です．
|
|
59
62
|
緑の部分がfor文の中で回っている部分です．
|
|
63
|
+
質問者のhnk_llさんはおそらく，
|
|
60
|
-
if文で
|
|
64
|
+
「if文で条件を絞って，エラトステネスの篩を実装しよう」
|
|
65
|
+
と思ったのかもしれません．
|
|
61
|
-
if文の条件文
|
|
66
|
+
しかし，この**if文の条件文が計算量の多い計算を含んでいるので，すごい時間がかかっているのです．**
|
|
62
|
-
これではすごい時間がかかってしまいます．無駄もあります．
|
|
63
67
|
|
|
68
|
+
## 解説2：どのように改善すればよいか
|
|
69
|
+
|
|
70
|
+
さて，どのように改善すれば速くなるかということですが，
|
|
64
|
-
|
|
71
|
+
このif文を使わずに実装することです．
|
|
72
|
+
|
|
73
|
+
具体的には，
|
|
65
74
|
i = 2のとき，j = 4 6 8 10 12 ...のときにbox[j]を0にし，
|
|
66
75
|
i = 3のとき，j = 6 9 12 15 18 ...のときにbox[j]を0にし…
|
|
67
|
-
というふうにiの倍数（ただし1倍を除く）
|
|
76
|
+
というふうにiの倍数（ただし1倍を除く）のときだけfor文を回るようにします．
|
|
77
|
+
そうすればif文は不要になります．
|
|
68
78
|
|
|
79
|
+
画像だとこうなります．（緑の部分がfor文の中で回っている部分です．）
|
|
80
|
+
緑の部分が減りましたね！
|
|
81
|
+
|
|
69
82
|
それが
|
|
70
83
|
```c
|
|
71
84
|
for (j = i + 1; j < 246913; j++)
|
|
@@ -73,5 +86,4 @@
|
|
|
73
86
|
box[j] = 1;
|
|
74
87
|
}
|
|
75
88
|
```
|
|
76
|
-
というふうにすれば速くなる理由です．
|
|
89
|
+
というふうにすれば速くなる理由です．
|
|
77
|
-
そしてこれが本来でいうところの「エラトステネスの篩」ですね．
|
4
画像を追加
answer
CHANGED
|
@@ -53,17 +53,19 @@
|
|
|
53
53
|
```
|
|
54
54
|
の部分で，j を1ずつ増やして，`j % i == 0 && box[j] == 0`が真のとき（つまり素数でないとき）にbox[j]を0にしていますね．
|
|
55
55
|
しかし，これだと，無駄が多いです．
|
|
56
|
-
というのも
|
|
57
|
-
|
|
58
|
-
|
|
59
|
-
|
|
56
|
+
というのも，下の画像を見てみてください．
|
|
57
|
+
|
|
58
|
+
この画像は従来の手法でした場合のfor文の中で回っている部分です．
|
|
59
|
+
緑の部分がfor文の中で回っている部分です．
|
|
60
|
+
if文で計算量を減らしていると思われますが，
|
|
61
|
+
if文の条件文自体が計算量の多い計算を含んでいるので，
|
|
60
62
|
これではすごい時間がかかってしまいます．無駄もあります．
|
|
61
63
|
|
|
62
64
|
ですので，もっと速くするためには
|
|
63
65
|
i = 2のとき，j = 4 6 8 10 12 ...のときにbox[j]を0にし，
|
|
64
66
|
i = 3のとき，j = 6 9 12 15 18 ...のときにbox[j]を0にし…
|
|
65
67
|
というふうにiの倍数（ただし1倍を除く）でif文を通るようにします．
|
|
66
|
-
|
|
68
|
+
|
|
67
69
|
それが
|
|
68
70
|
```c
|
|
69
71
|
for (j = i + 1; j < 246913; j++)
|
|
@@ -71,4 +73,5 @@
|
|
|
71
73
|
box[j] = 1;
|
|
72
74
|
}
|
|
73
75
|
```
|
|
74
|
-
というふうにすれば速くなる理由です．
|
|
76
|
+
というふうにすれば速くなる理由です．
|
|
77
|
+
そしてこれが本来でいうところの「エラトステネスの篩」ですね．
|
3
box[j]を0にするという記述を追加・変更
answer
CHANGED
|
@@ -51,7 +51,7 @@
|
|
|
51
51
|
box[j] = 1;
|
|
52
52
|
}
|
|
53
53
|
```
|
|
54
|
-
の部分で，j を1ずつ増やして，`j % i == 0 && box[j] == 0`が真のとき（つまり素数でないとき）に
|
|
54
|
+
の部分で，j を1ずつ増やして，`j % i == 0 && box[j] == 0`が真のとき（つまり素数でないとき）にbox[j]を0にしていますね．
|
|
55
55
|
しかし，これだと，無駄が多いです．
|
|
56
56
|
というのも
|
|
57
57
|
i = 2のとき，j = 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...をif文で判定し，
|
|
@@ -60,8 +60,8 @@
|
|
|
60
60
|
これではすごい時間がかかってしまいます．無駄もあります．
|
|
61
61
|
|
|
62
62
|
ですので，もっと速くするためには
|
|
63
|
-
i = 2のとき，j = 4 6 8 10 12 ...
|
|
63
|
+
i = 2のとき，j = 4 6 8 10 12 ...のときにbox[j]を0にし，
|
|
64
|
-
i = 3のとき，j = 6 9 12 15 18 ...
|
|
64
|
+
i = 3のとき，j = 6 9 12 15 18 ...のときにbox[j]を0にし…
|
|
65
65
|
というふうにiの倍数（ただし1倍を除く）でif文を通るようにします．
|
|
66
66
|
|
|
67
67
|
それが
|
2
ifのくだりを修正
answer
CHANGED
|
@@ -60,8 +60,8 @@
|
|
|
60
60
|
これではすごい時間がかかってしまいます．無駄もあります．
|
|
61
61
|
|
|
62
62
|
ですので，もっと速くするためには
|
|
63
|
-
i = 2のとき，j = 4 6 8 10 12 ...
|
|
63
|
+
i = 2のとき，j = 4 6 8 10 12 ...
|
|
64
|
-
i = 3のとき，j = 6 9 12 15 18 ...
|
|
64
|
+
i = 3のとき，j = 6 9 12 15 18 ...
|
|
65
65
|
というふうにiの倍数（ただし1倍を除く）でif文を通るようにします．
|
|
66
66
|
|
|
67
67
|
それが
|
1
文章の小さな修正
answer
CHANGED
|
@@ -51,7 +51,7 @@
|
|
|
51
51
|
box[j] = 1;
|
|
52
52
|
}
|
|
53
53
|
```
|
|
54
|
-
の部分で，j を1ずつ増やして，`j%i==0&&box[j]==0`（つまり素数でない
|
|
54
|
+
の部分で，j を1ずつ増やして，`j % i == 0 && box[j] == 0`が真のとき（つまり素数でないとき）に配列の中身を0にしていますね．
|
|
55
55
|
しかし，これだと，無駄が多いです．
|
|
56
56
|
というのも
|
|
57
57
|
i = 2のとき，j = 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...をif文で判定し，
|
|
@@ -60,9 +60,10 @@
|
|
|
60
60
|
これではすごい時間がかかってしまいます．無駄もあります．
|
|
61
61
|
|
|
62
62
|
ですので，もっと速くするためには
|
|
63
|
-
i = 2のとき，j = 4 6 8 10 12...
|
|
63
|
+
i = 2のとき，j = 4 6 8 10 12 ...をif文で判定し，
|
|
64
|
-
i = 3のとき，j = 6 9 12 15 18...
|
|
64
|
+
i = 3のとき，j = 6 9 12 15 18 ...をif文で判定し…
|
|
65
65
|
というふうにiの倍数（ただし1倍を除く）でif文を通るようにします．
|
|
66
|
+
|
|
66
67
|
それが
|
|
67
68
|
```c
|
|
68
69
|
for (j = i + 1; j < 246913; j++)
|