エラトステネスのふるい

プログラミングメモ
エラトステネスのふるいというアルゴリズムを初めて使ってみたので、忘れないようにメモ

AOJ 0009 Prime Number

AOJ 0009 の問題
整数n以下の素数の数を出力するという問題です。

はじめは試し割りみたいな感じでやってみたんですが、TimeLimitになってしまったので。エラトステネスのふるいというアルゴリズムを使ってみました。

とりあえず書いてみたプログラムが以下のもの

エラトステネスのふるい

#include <iostream>
using namespace std;
#define MAX 10000000
bool prime[MAX]={true};

int countPrime(int n){
	if(n<2) return 0;
	if(n==2) return 1;
	int ret=0;
	for(int i=0;i<MAX;i++) prime[i]=true;
	for(int i=2;i*i<=n;i++){
		if(prime[i]){
			for(int j=i*i;j<=n;j=j+i){
				prime[j]=false;
			}
		}
	}
	for(int i=2;i<=n;i++){
		if(prime[i]) ret++;
	}
	return ret;
}

int main(){
	int n;
	while(cin>>n){
		cout <<countPrime(n) <<endl;		
	}
	return 0;
}

エラトステネスのふるいはO(n)らしいのでかなり高速です。

アルゴリズムについてはwikipediaをみるとわかりやすかったです。

このブログを書いてて気づきましたがこの問題の場合複数の入力があり、入力されるnは６桁という制約があるので、入力されたnに対して毎回数え直すのではなく、
1000000まで一度ループを回して素数を決めてしまって、その後に入力されたnまでの素数を数えるっていう風にしたほうがよさそうですね。