素数表

Java Algorithm

Project Euler をやっている人は素数関係の部分をライブラリ化するに違いないと思う今日この頃ですが、エラトステネスの篩だろ、常識的普通に考えて。

% time java Prime 1 50000000
java Prime 1 50000000  31.50s user 0.35s system 104% cpu 30.381 total

% time java Prime 2 50000000
java Prime 2 50000000  1.50s user 0.18s system 106% cpu 1.573 total

% time java Prime 3 50000000
java Prime 3 50000000  0.95s user 0.13s system 135% cpu 0.797 total

上から、素数で順番に剰余を求めるもの、エラトステネスの篩、エラトステネスの篩で配列の代わりに BitSet を使うもの。BitSet が速いのはちょっと意外だった。
ちなみに、10^12 とかになると、Miller-Rabin test でも使って素数判定しないと無理です。

import java.util.BitSet;
import java.util.List;
import java.util.ArrayList;

public class Prime {
    public static void main(String[] args) {
        if (args.length != 2) {
            usage();
        }

        int mode = Integer.parseInt(args[0]);
        int n = Integer.parseInt(args[1]);
        List<Integer> primes;
        switch (mode) {
            case 1:
                primes = primes1(n);
                break;

            case 2:
                primes = primes2(n);
                break;

            case 3:
                primes = primes3(n);
                break;

            default:
                usage();
                break;
        }
    }

    private static void usage() {
        System.err.println("Usage: java + " + Prime.class.getName() + " (1|2)");
        System.exit(2);
    }

    public static List<Integer> primes1(int n) {
        List<Integer> primes = new ArrayList<Integer>();
        primes.add(2);
        i: for (int i = 3; i <= n; i += 2) {
            for (int prime : primes) {
                if (prime * prime > i) break;
                if (i % prime == 0) continue i;
            }
            primes.add(i);
        }
        return primes;
    }

    public static List<Integer> primes2(int n) {
        List<Integer> primes = new ArrayList<Integer>();
        primes.add(2);
        boolean[] table = new boolean[n / 2 + 1];
        int limit = (int) Math.sqrt(n);
        for (int i = 3; i <= limit; i += 2) {
            if (table[i / 2]) { continue; }
            for (int j = i * i; j <= n; j += i * 2) {
                table[j / 2] = true;
            }
        }

        for (int i = 1; i < table.length; i++) {
            if (!table[i]) {
                primes.add(2 * i + 1);
            }
        }

        if (primes.get(primes.size() - 1) > n) {
            primes.remove(primes.size() - 1);
        }

        return primes;
    }

    public static List<Integer> primes3(int n) {
        BitSet table = new BitSet(n / 2 + 1);
        table.set(1, n / 2 + n % 2);

        int limit = (int) Math.sqrt(n);
        for (int i = 3; i <= limit; i += 2) {
            if (!table.get(i / 2)) { continue; }
            for (int j = i * i; j <= n; j += i * 2) {
                table.clear(j / 2);
            }
        }

        List<Integer> primes = new ArrayList<Integer>();
        primes.add(2);
        for (int i = table.nextSetBit(0); i >= 0; i = table.nextSetBit(i + 1)) {
            primes.add(2 * i + 1);
        }

        if (primes.get(primes.size() - 1) > n) {
            primes.remove(primes.size() - 1);
        }

        return primes;
    }
}