先日参加したAtCoderでも必要になったので、素数判定処理と、エラトステネスの篩を使った素数列挙処理を作りました。
列挙のほうはコレだとprintしているだけなので、好みのデータ型に持たせる必要があります。
素数判定処理&エラトステネスの篩
// ルートxまで
public boolean isPrime(int x) {
for (int i = 2; i*i <= x; i++) {
if (x % i == 0) {
System.out.println(x + "is divisible by " + i);
return false;
}
}
return true;
}
// 指定したx以下の素数をリストアップする
public void sieveOfEratosthenes(int x) {
IntStream.rangeClosed(2, x)
.filter(i -> IntStream.rangeClosed(2, (int)Math.sqrt(i))
.allMatch(j -> i%j !=0))
.forEach(n -> {
System.out.println(n);
});
}
参考
- エラトステネスの篩 – Wikipedia
- 篩にかけている様子がグラフィカルに出ているのでわかりやすい。
- Prime numbers with Java8 Stream API
- 篩のほうはこちらの丸パクリです。