AOJ - Problem 0009 : Prime Number

• 問題文

n以下の素数の個数を出力する問題です。
１は素数ではないので気をつけましょう。
素数の問題ではエラトステネスのふるいを使うことが多いです。
エラトステネスのふるいについての説明はwikipediaに詳しく載っています。
とてもわかりやすいので一度見た方がいいかもしれません。

#include <iostream>
#include <cmath>
using namespace std;
#define MAX 1000000

int main(){
	bool p[MAX+1];
	int n, ans;

	for(int i=0 ; i<=MAX ; i++){
		p[i] = (i<=1)? false : true ;
	}

	for(int i=2 ; i<=sqrt(MAX)+1 ; i++){
		if(p[i]){
			for(int j=i*2 ; j<=MAX ; j+=i){
				p[j] = false;
			}
		}
	}

	while( cin >> n ){		
		ans = 0;
		for(int i=0 ; i<=n ; i++){
			if(p[i]){
				ans++;
			}
		}
		cout << ans << endl;
	}
}