回答編集履歴

1

加筆

2021/05/29 04:52

投稿

episteme
episteme

スコア16612

test CHANGED
@@ -5,3 +5,43 @@
5
5
 
6
6
 
7
7
  異なる(そもそもやることが違う)ふたつを比較することに意味があるんですか?
8
+
9
+
10
+
11
+ [おあそび] 初回を除きめっちゃ速いやつ
12
+
13
+ ```C++
14
+
15
+ bool IsPrime(int num) {
16
+
17
+ // エラトステネスの篩, 素数かどうかの配列を作る
18
+
19
+ static std::vector<bool> prime_array(100005, true);
20
+
21
+ if ( !prime_array[2] ) {
22
+
23
+ prime_array[0] = false;
24
+
25
+ prime_array[1] = false;
26
+
27
+ for (int i = 2; i * i <= 100000; i++) {
28
+
29
+ if (!prime_array[i]) continue;
30
+
31
+ // 素数のn倍(n>1)に関してはfalseにする
32
+
33
+ for (int j = i * 2; j <= 100000; j += i) {
34
+
35
+ prime_array[j] = false;
36
+
37
+ }
38
+
39
+ }
40
+
41
+ }
42
+
43
+ return prime_array[num];
44
+
45
+ }
46
+
47
+ ```