---
title: エラトステネスの篩
tags: []
categories: ["Programming", "Algorithm", "PrimeNumber", "SieveOfEratosthenes"]
date: 2011-06-07T18:19:32Z
updated: 2011-06-07T18:19:32Z
---

基礎おさらい素数編その2

n以下の素数を列挙する手法について。

2以上n以下の整数を全て挙げ、そこから2で割り切れるものをのぞき、残ったうちから3で割り切れるものをのぞき、残ったうちから … mで割り切れるものをのぞく、というのを繰り返していくことで列挙できる。

    private static int MAX_N = 10000;
    private static boolean[] isPrime = new boolean[MAX_N + 1]; // iが素数かどうか

    public static List<Integer> sieve(int n) {
        List<Integer> res = new ArrayList<Integer>();
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (isPrime[i]) {
                res.add(i);
                for (int j = 2 * i; j <= n; j += i) {
                    // iをのぞくiの倍数を全てのぞく
                    isPrime[j] = false;
                }
            }
        }
        Collections.sort(res);
        return res;
    }