JavaのStreamAPIで素数列挙をする

目次

JavaのStreamAPIを使って2から自然数Nまでの素数列挙をしてみます。

実装できたのは試し割りによる普通のアルゴリズムです。（少し最適化はしますが。）

エラトステネスの篩を実装したかったのですができませんでした。それでもエラトステネスの篩と比較しても一長一短のある実装となります。

以下では3つの実装を紹介します。

$ \sqrt{N} $までの自然数で試し割り

一番直感的な実装です。

static IntStream primes1(int N) {
    IntPredicate isPrime = i ->
            IntStream.iterate(2, j -> j * j <= i, j -> j + 1).allMatch(j -> i % j != 0);

    return IntStream.rangeClosed(2, N).filter(isPrime);
}

実行例

primes1(100).forEach(i -> System.out.print(i + ","));
// 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,

$ \sqrt{N} $までの素数で試し割り

上の実装を少し最適化したものです。試し割りに使う数がかなり減ります。

static IntStream primes2(int N) {
    int[] startPrimes = primes1((int) Math.sqrt(N)).toArray();
    int midPrime = startPrimes[startPrimes.length - 1];

    IntPredicate isPrime = i -> Arrays.stream(startPrimes).allMatch(j -> i % j != 0);
    IntStream endPrimes = IntStream.iterate(midPrime + 2, i -> i <= N, i -> i + 2).filter(isPrime);
    return IntStream.concat(Arrays.stream(startPrimes), endPrimes);
}

実行例

primes2(100).forEach(i -> System.out.print(i + ","));
// 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,

エラトステネスの篩

エラトステネスの篩の有名なboolean配列による実装です。StreamAPIは使ってませんが比較用に使っていきます。

この実装は配列のランダムアクセス性を使って無駄なく非素数フラグを立てていきます。

参考　 JavaのStream APIでエラトステネスの篩 - tomoesaturnのブログ

static IntStream eratosthenes(int N) {
    boolean[] notPrime = new boolean[N - 1];
    int sqrt = (int) Math.sqrt(N);

    for (int i = 0; i + 2 <= sqrt; i++) {
        if (!notPrime[i]) {
            for (int j = 2; (i + 2) * j <= N; j++) {
                notPrime[(i + 2) * j - 2] = true;
            }
        }
    }
    return IntStream.range(0, N - 1).filter(i -> !notPrime[i]).map(i -> i + 2);
}

eratosthenes(100).forEach(i -> System.out.print(i + ","));
// 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,

速度比較

以上の3つの実装の速度を計測します。

public static void main(String[] args) {
    int N = 10000000;

    long s = System.currentTimeMillis();
    System.out.println(primes1(N).count());
    System.out.println(System.currentTimeMillis() - s);
    System.out.println();

    s = System.currentTimeMillis();
    System.out.println(primes2(N).count());
    System.out.println(System.currentTimeMillis() - s);
    System.out.println();

    s = System.currentTimeMillis();
    System.out.println(eratosthenes(N).count());
    System.out.println(System.currentTimeMillis() - s);
}

結果

664579
13333

664579
2185

664579
110

やはりエラトステネスの篩は早いですね。

計算量・メモリ消費

以上の3つの計算量とメモリ消費についてまとめます。

アルゴリズム	計算量	メモリ消費
$ \sqrt{N} $までの自然数で試し割り	$ O(N\sqrt{N}) $	$ O(1) $
$ \sqrt{N} $までの素数で試し割り	$O(N\sqrt{N} / \log N ) $	$O(\sqrt{N} / \log N ) $
エラトステネスの篩	$ O(N \log \log N) $	$ O(N) $

自然数Nまでの素数の個数は素数定理より$O(N / \log N ) $ のオーダーで増加しますので、$ \sqrt{N} $までの素数の個数は$O(\sqrt{N} / \log N ) $ で増加します。

2番目のアルゴリズムは $ \sqrt{N} $ までの素数の配列を用意するのに $ O(\sqrt{N}\sqrt{\sqrt{N}}) $ だけの計算量がかかりますが、試し割り処理の$O(N\sqrt{N} / \log N ) $ の方が支配的になりますので表のようになっています。

この表では計算量は下にあるアルゴリズムが小さくて、メモリ消費は上にあるアルゴリズムの方が小さくなりました。

2番目のアルゴリズムはエラトステネスの篩よりは計算量が多いけど、メモリ消費は小さいものとなりました。そしてStreamAPIを使って副作用なく実装できてるので並列化もしやすいと思います。