エラトステネスの篩 vs アトキンの篩


エラトステネスの篩とアトキンの篩って実際どのぐらい違うのか気になったのでー

エラトステネスの篩

倍々しながら篩から落としていくアレです。

public interface Primes {

    /**
     * Sieve of Eratosthenes.
     * @param upperBound upper bound
     * @return List of prime factor
     */
    static List<Integer> eratosthenes(int upperBound) {

        boolean[] isComposite = new boolean[upperBound + 1];
        int upperBoundSqrt = (int) Math.sqrt(upperBound);

        for (int i = 2; i <= upperBoundSqrt; i++) {
            if (!isComposite[i]) {
                for (int j = i * i; j <= upperBound; j += i)
                    isComposite[j] = true;
            }
        }

        List<Integer> list = new ArrayList<>();
        for (int m = 2; m <= upperBound; m++) {
            if (!isComposite[m]) list.add(m);
        }
        return list;
    }
}

アトキンの篩

一方アトキンは少し複雑。

public interface Primes {

    /**
     * Sieve of Atkin.
     * @param upperBound upper bound
     * @return List of prime factor
     */
    static List<Integer> atkin(int upperBound) {
        
        boolean[] sieve = new boolean[upperBound + 1];
        int upperBoundSqrt = (int) Math.sqrt(upperBound);

        sieve[0] = sieve[1] = false;
        sieve[2] = sieve[3] = true;

        for (int x = 1; x <= upperBoundSqrt; x++) {
            for (int y = 1; y <= upperBoundSqrt; y++) {
                int n = (4 * x * x) + (y * y);
                if (n <= upperBound && (n % 12 == 1 || n % 12 == 5)) {
                    sieve[n] = !sieve[n];
                }
                n = (3 * x * x) + (y * y);
                if (n <= upperBound && (n % 12 == 7)) {
                    sieve[n] = !sieve[n];
                }
                n = (3 * x * x) - (y * y);
                if (x > y && n <= upperBound && (n % 12 == 11)) {
                    sieve[n] = !sieve[n];
                }
            }
        }

        for (int n = 5; n <= upperBoundSqrt; n++) {
            if (sieve[n]) {
                int x = n * n;
                for (int i = x; i <= upperBound; i += x) {
                    sieve[i] = false;
                }
            }
        }

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i <= upperBound; i++) {
            if (sieve[i]) list.add(i);
        }
        return list;
    }
}

エラトステネスの篩 vs アトキンの篩

10回試行してみる。

final int upperBound = 10_000_000;

LongSummaryStatistics eratosthenes = IntStream.range(0, 10).mapToLong(i -> {
    long start = System.currentTimeMillis();
    Primes.eratosthenes(upperBound);
    return System.currentTimeMillis() - start;
}).summaryStatistics();

LongSummaryStatistics atkin = IntStream.range(0, 10).mapToLong(i -> {
    long start = System.currentTimeMillis();
    Primes.atkin(upperBound);
    return System.currentTimeMillis() - start;
}).summaryStatistics();

System.out.println("eratosthenes : " + eratosthenes);
System.out.println("atkin        : " + atkin);

結果

アトキンが少し早いみたいですね。

eratosthenes : LongSummaryStatistics{count=10, sum=1892, min=142, average=189.200000, max=277}
atkin        : LongSummaryStatistics{count=10, sum=1754, min=144, average=175.400000, max=251}

それにしても summaryStatistics() が便利です。

おまけ

素因数分解は以下でよろし。

    static List<Integer> factorization(int x) {
        List<Integer> result = new ArrayList<>();

        while (x >= 4 && x % 2 == 0) {
            result.add(2);
            x /= 2;
        }
        int d = 3;
        int q = x / d;
        while (q >= d) {
            if (x % d == 0) {
                result.add(d);
                x = q;
            } else {
                d += 2;
            }
            q = x / d;
        }
        result.add(x);
        return result;
    }

Spock のテストケースは以下のようになります。

def "Compute factorization"() {
    expect:
    Primes.factorization(arg).stream()
          .map({it -> it.toString()})
          .collect(Collectors.joining(",")) == result

    where:
    arg    |  result
    2      |  "2"
    3      |  "3"
    360    |  "2,2,2,3,3,5"
    8633   |  "89,97"
    295883 |  "7,43,983"
}

まとめ

summaryStatistics() 便利。

Spock も便利。