回答編集履歴
6
ikadzuchiさんからの引用
test
CHANGED
|
@@ -128,7 +128,9 @@
|
|
|
128
128
|
|
|
129
129
|
と思ったのかもしれません．
|
|
130
130
|
|
|
131
|
-
しかし，この**if文の条件文が計算量の多い計算を含んでいるので，すごい時間がかかっているのです．
|
|
131
|
+
しかし，この**if文の条件文が計算量の多い計算を含んでいるので，すごい時間がかかっている**のです．
|
|
132
|
+
|
|
133
|
+
ikadzuchiさんのおっしゃるとおり，除算や剰余はたいへん遅い処理なのです…
|
|
132
134
|
|
|
133
135
|
|
|
134
136
|
|
5
見出しを付けた
test
CHANGED
|
@@ -1,3 +1,7 @@
|
|
|
1
|
+
## 結論
|
|
2
|
+
|
|
3
|
+
|
|
4
|
+
|
|
1
5
|
hnk_llさんのソースコードが以下の通りですね．
|
|
2
6
|
|
|
3
7
|
|
|
@@ -88,6 +92,8 @@
|
|
|
88
92
|
|
|
89
93
|
|
|
90
94
|
|
|
95
|
+
## 解説1：なぜ従来の手法が遅いのか
|
|
96
|
+
|
|
91
97
|
従来の手法ですと，
|
|
92
98
|
|
|
93
99
|
```c
|
|
@@ -116,23 +122,43 @@
|
|
|
116
122
|
|
|
117
123
|
緑の部分がfor文の中で回っている部分です．
|
|
118
124
|
|
|
119
|
-
|
|
125
|
+
質問者のhnk_llさんはおそらく，
|
|
120
126
|
|
|
121
|
-
if文
|
|
127
|
+
「if文で条件を絞って，エラトステネスの篩を実装しよう」
|
|
122
128
|
|
|
129
|
+
と思ったのかもしれません．
|
|
130
|
+
|
|
123
|
-
こ
|
|
131
|
+
しかし，この**if文の条件文が計算量の多い計算を含んでいるので，すごい時間がかかっているのです．**
|
|
124
132
|
|
|
125
133
|
|
|
126
134
|
|
|
135
|
+
## 解説2：どのように改善すればよいか
|
|
136
|
+
|
|
137
|
+
|
|
138
|
+
|
|
139
|
+
さて，どのように改善すれば速くなるかということですが，
|
|
140
|
+
|
|
127
|
-
|
|
141
|
+
このif文を使わずに実装することです．
|
|
142
|
+
|
|
143
|
+
|
|
144
|
+
|
|
145
|
+
具体的には，
|
|
128
146
|
|
|
129
147
|
i = 2のとき，j = 4 6 8 10 12 ...のときにbox[j]を0にし，
|
|
130
148
|
|
|
131
149
|
i = 3のとき，j = 6 9 12 15 18 ...のときにbox[j]を0にし…
|
|
132
150
|
|
|
133
|
-
というふうにiの倍数（ただし1倍を除く）
|
|
151
|
+
というふうにiの倍数（ただし1倍を除く）のときだけfor文を回るようにします．
|
|
152
|
+
|
|
153
|
+
そうすればif文は不要になります．
|
|
134
154
|
|
|
135
155
|
|
|
156
|
+
|
|
157
|
+
画像だとこうなります．（緑の部分がfor文の中で回っている部分です．）
|
|
158
|
+
|
|
159
|
+
緑の部分が減りましたね！
|
|
160
|
+
|
|
161
|
+
|
|
136
162
|
|
|
137
163
|
それが
|
|
138
164
|
|
|
@@ -149,5 +175,3 @@
|
|
|
149
175
|
```
|
|
150
176
|
|
|
151
177
|
というふうにすれば速くなる理由です．
|
|
152
|
-
|
|
153
|
-
そしてこれが本来でいうところの「エラトステネスの篩」ですね．
|
4
画像を追加
test
CHANGED
|
@@ -108,13 +108,17 @@
|
|
|
108
108
|
|
|
109
109
|
しかし，これだと，無駄が多いです．
|
|
110
110
|
|
|
111
|
-
というのも
|
|
111
|
+
というのも，下の画像を見てみてください．
|
|
112
112
|
|
|
113
|
-
|
|
113
|
+
|
|
114
114
|
|
|
115
|
-
|
|
115
|
+
この画像は従来の手法でした場合のfor文の中で回っている部分です．
|
|
116
116
|
|
|
117
|
+
緑の部分がfor文の中で回っている部分です．
|
|
118
|
+
|
|
119
|
+
if文で計算量を減らしていると思われますが，
|
|
120
|
+
|
|
117
|
-
|
|
121
|
+
if文の条件文自体が計算量の多い計算を含んでいるので，
|
|
118
122
|
|
|
119
123
|
これではすごい時間がかかってしまいます．無駄もあります．
|
|
120
124
|
|
|
@@ -128,7 +132,7 @@
|
|
|
128
132
|
|
|
129
133
|
というふうにiの倍数（ただし1倍を除く）でif文を通るようにします．
|
|
130
134
|
|
|
131
|
-
|
|
135
|
+
|
|
132
136
|
|
|
133
137
|
それが
|
|
134
138
|
|
|
@@ -145,3 +149,5 @@
|
|
|
145
149
|
```
|
|
146
150
|
|
|
147
151
|
というふうにすれば速くなる理由です．
|
|
152
|
+
|
|
153
|
+
そしてこれが本来でいうところの「エラトステネスの篩」ですね．
|
3
box[j]を0にするという記述を追加・変更
test
CHANGED
|
@@ -104,7 +104,7 @@
|
|
|
104
104
|
|
|
105
105
|
```
|
|
106
106
|
|
|
107
|
-
の部分で，j を1ずつ増やして，`j % i == 0 && box[j] == 0`が真のとき（つまり素数でないとき）に
|
|
107
|
+
の部分で，j を1ずつ増やして，`j % i == 0 && box[j] == 0`が真のとき（つまり素数でないとき）にbox[j]を0にしていますね．
|
|
108
108
|
|
|
109
109
|
しかし，これだと，無駄が多いです．
|
|
110
110
|
|
|
@@ -122,9 +122,9 @@
|
|
|
122
122
|
|
|
123
123
|
ですので，もっと速くするためには
|
|
124
124
|
|
|
125
|
-
i = 2のとき，j = 4 6 8 10 12 ...
|
|
125
|
+
i = 2のとき，j = 4 6 8 10 12 ...のときにbox[j]を0にし，
|
|
126
126
|
|
|
127
|
-
i = 3のとき，j = 6 9 12 15 18 ...
|
|
127
|
+
i = 3のとき，j = 6 9 12 15 18 ...のときにbox[j]を0にし…
|
|
128
128
|
|
|
129
129
|
というふうにiの倍数（ただし1倍を除く）でif文を通るようにします．
|
|
130
130
|
|
2
ifのくだりを修正
test
CHANGED
|
@@ -122,9 +122,9 @@
|
|
|
122
122
|
|
|
123
123
|
ですので，もっと速くするためには
|
|
124
124
|
|
|
125
|
-
i = 2のとき，j = 4 6 8 10 12 ...
|
|
125
|
+
i = 2のとき，j = 4 6 8 10 12 ...
|
|
126
126
|
|
|
127
|
-
i = 3のとき，j = 6 9 12 15 18 ...
|
|
127
|
+
i = 3のとき，j = 6 9 12 15 18 ...
|
|
128
128
|
|
|
129
129
|
というふうにiの倍数（ただし1倍を除く）でif文を通るようにします．
|
|
130
130
|
|
1
文章の小さな修正
test
CHANGED
|
@@ -104,7 +104,7 @@
|
|
|
104
104
|
|
|
105
105
|
```
|
|
106
106
|
|
|
107
|
-
の部分で，j を1ずつ増やして，`j%i==0&&box[j]==0`（つまり素数でない
|
|
107
|
+
の部分で，j を1ずつ増やして，`j % i == 0 && box[j] == 0`が真のとき（つまり素数でないとき）に配列の中身を0にしていますね．
|
|
108
108
|
|
|
109
109
|
しかし，これだと，無駄が多いです．
|
|
110
110
|
|
|
@@ -122,11 +122,13 @@
|
|
|
122
122
|
|
|
123
123
|
ですので，もっと速くするためには
|
|
124
124
|
|
|
125
|
-
i = 2のとき，j = 4 6 8 10 12...
|
|
125
|
+
i = 2のとき，j = 4 6 8 10 12 ...をif文で判定し，
|
|
126
126
|
|
|
127
|
-
i = 3のとき，j = 6 9 12 15 18...
|
|
127
|
+
i = 3のとき，j = 6 9 12 15 18 ...をif文で判定し…
|
|
128
128
|
|
|
129
129
|
というふうにiの倍数（ただし1倍を除く）でif文を通るようにします．
|
|
130
|
+
|
|
131
|
+
|
|
130
132
|
|
|
131
133
|
それが
|
|
132
134
|
|