AOJ:0009

gistfile1.java

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		while(scn.hasNext()) {
			int n = scn.nextInt();
			if (n == 1) { //n = 1のとき、素数の数は0
				System.out.println(0);
				continue;
			}
			if (n == 2) { //n = 2のとき、素数の数は1
				System.out.println(1);
				continue;
			}
			//素数判定用の配列作成。nが素数のときx[n] = true
			//x[0]は使用しないので要素数n + 1の配列を作成
			boolean[] x = new boolean[n + 1];
			x[2] = true; //2は素数なのでtrue
			//偶数は素数じゃないので3以上の奇数をとりあえずtrue
			for (int i = 3; i <= n; i += 2) {
				x[i] = true;
			}
			//d = 3から篩スタート。
			int d = 3;
			while (d * d <= n) {
				//dの倍数をfalse
				for (int i = d * d; i <= n; i += d) {
					x[i] = false;
				}
				//dの次の素数を探してdに代入
				for  (int i = d + 1; i <= n; i++) {
					if (x[i] == true) {
						d = i;
						break;
					}
				}
			}
			//結果表示
			int cnt = 0;
			for (int i = 2; i <= n; i++) {
				if (x[i]) {
					cnt++;
				}
			}
			System.out.println(cnt);
		}
	}
}