0009-Prime Number

問題（外部リンク）

Prime Number | Aizu Online Judge

実装の概要

あるnが素数かどうかだけでなく、nまでの素数の個数を求める問題なので2,3,...nのように1つ1つ素数かどうかをチェックしていると間に合いません。
そのため、事前に「その数が素数かどうか」を格納するための配列を作成します。その際にエラトステネスの篩を用いることで効率良く判定を行うことができます。
エラトステネスの篩 - Wikipedia
簡単に言うと、例として「3は素数だが、明らかにその他の3の倍数は素数ではないので事前にfalseにしておく」ということです。
なお、外側のループはnまで回す必要はありません。証明はここでは行いませんがまでで十分です。
今回の問題では入力は999,999までですが、実装例のように余分に配列を作成しても十分間に合います。他の問題でも素数判定はよく取り上げられるので、あらかじめそのためのクラスを作成しておくと便利かもしれません。

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        PrimeNumberGenerator png = new PrimeNumberGenerator();

        while(true){
            String tmpStr = br.readLine();
            if(tmpStr == null){
                break;
            }

            int n = Integer.parseInt(tmpStr);

            int count = 0;
            for(int i = 2; i <= n; i++){
                if(png.isPrime(i)){
                    count++;
                }
            }

            System.out.println(count);
        }
    }

}

class PrimeNumberGenerator {
    private final int N = 100000000;
    private boolean[] isPrime= new boolean[N + 1];

    public PrimeNumberGenerator() {
        Arrays.fill(isPrime, true);

        isPrime[0] = false;
        isPrime[1] = false;

        int limit = (int)Math.sqrt(N);
        for(int i = 2; i <= limit ; i++){

            if(isPrime[i] == false){
                continue;
            }

            for(int j = i * 2; j <= N; j += i){
                isPrime[j] = false;
            }
        }
    }

    public boolean isPrime(int index){
        return isPrime[index];
    }
}