回答編集履歴
3
追記
answer
CHANGED
|
@@ -21,7 +21,7 @@
|
|
|
21
21
|
return true;
|
|
22
22
|
}
|
|
23
23
|
|
|
24
|
-
static void
|
|
24
|
+
static void func(final int num) {
|
|
25
25
|
HashSet<Integer> primes = new LinkedHashSet<>();
|
|
26
26
|
primes.add(2);// 最初の素数2を初期値として格納しておく
|
|
27
27
|
int i = 1;// 最初のループでi=1+2=3となり3から素数判定する
|
2
追記
answer
CHANGED
|
@@ -7,8 +7,42 @@
|
|
|
7
7
|
[Collections#binarySearch](https://docs.oracle.com/javase/jp/9/docs/api/java/util/Collections.html#binarySearch-java.util.List-T-java.util.Comparator-)
|
|
8
8
|
|
|
9
9
|
|
|
10
|
-
素数は重複値が存在しないので、[
|
|
10
|
+
素数は重複値が存在しないので、[LinkedHashSet](https://docs.oracle.com/javase/jp/8/docs/api/java/util/LinkedHashSet.html)や[BitSet](https://docs.oracle.com/javase/jp/9/docs/api/java/util/BitSet.html)を使ってくださいな。
|
|
11
11
|
|
|
12
|
+
```Java
|
|
13
|
+
static boolean isPrime(final int x) {
|
|
14
|
+
// 平方根まで判定すれば、良いです。
|
|
15
|
+
final double sqrtNum = Math.sqrt(x);
|
|
16
|
+
for (int i = 3; i <= sqrtNum; i += 2) {
|
|
17
|
+
if (x % i == 0) {
|
|
18
|
+
return false;
|
|
19
|
+
}
|
|
20
|
+
}
|
|
21
|
+
return true;
|
|
22
|
+
}
|
|
23
|
+
|
|
24
|
+
static void func2(final int num) {
|
|
25
|
+
HashSet<Integer> primes = new LinkedHashSet<>();
|
|
26
|
+
primes.add(2);// 最初の素数2を初期値として格納しておく
|
|
27
|
+
int i = 1;// 最初のループでi=1+2=3となり3から素数判定する
|
|
28
|
+
int last_prime = 0;
|
|
29
|
+
while (primes.size() < num) {
|
|
30
|
+
i += 2;// 偶数をスキップ
|
|
31
|
+
if (isPrime(i)) {
|
|
32
|
+
primes.add(i);
|
|
33
|
+
last_prime = i;
|
|
34
|
+
}
|
|
35
|
+
}
|
|
36
|
+
// sizeを使わなくても、引数のnumと最後の素数を変数に退避しておけばよいです。
|
|
37
|
+
System.out.println(num + ":" + last_prime);
|
|
38
|
+
}
|
|
39
|
+
```
|
|
40
|
+
10001:104743
|
|
41
|
+
22ms
|
|
42
|
+
|
|
43
|
+
■参考情報
|
|
44
|
+
[エラトステネスの篩で調べる 素数判定の上限と平方根の関係性](http://szarny.hatenablog.com/entry/2017/09/28/003352)
|
|
45
|
+
|
|
12
46
|
---
|
|
13
47
|
プログラムのどこに時間がかかっているのかを調べたい時はプロファイラーを使います。
|
|
14
48
|
JDKに付属しているのだと[jvisualvm](http://www.techscore.com/blog/2017/12/11/identifying_performance_bottlenecks_with_jvisualvm/)とかでしょうか。
|
1
追記
answer
CHANGED
|
@@ -1,4 +1,4 @@
|
|
|
1
|
-
[ArrayList](https://docs.oracle.com/javase/jp/9/docs/api/java/util/ArrayList.html)は要素が動的に変更できる点以外は配列と同じなので存在チェックは配列と同じで内部の要素を全部たどります。
|
|
1
|
+
[ArrayList](https://docs.oracle.com/javase/jp/9/docs/api/java/util/ArrayList.html)は要素数が動的に変更できる点以外は配列と同じなので存在チェックは配列と同じで内部の要素を全部たどります。
|
|
2
2
|
|
|
3
3
|
> Listインタフェースのサイズ変更可能な配列の実装です。
|
|
4
4
|
|