エラトステネスのふるい(素数)

最近、課題で「１～ｎまでの素数を求めよ」という問題が出てきました


最初頑張って書いてみたコード↓

//nまでの素数を数えるメソッド
public int countPrimeNumber(int n){

	//nまでの整数の配列
	boolean[] notPrime = new boolean[n+1];

	//素数以外は真とする
	for(int i=2; i<=n; i++){
		for(int j=i*2; j<=n; j+=i){
			notPrime[j] = true;
		}
	}

	//真以外を足し合わせる
	int count = 0;
	for(int i=2; i<=n; i++){
		if(!notPrime[i]){
			count++;
		}
	}

　　　　return count;
}

一応これでちゃんと素数の数が出るけど、n=１億、とかになってくると超遅いので書き直しました



修正後↓

public int countPrimeNumber(int n){
	
	//nまでの整数の配列（0を含む）
	boolean[] notPrime = new boolean[n+1];
		
	//素数以外を真とする(偶数は除外）
	for(int i=3; i<=Math.sqrt(n); i+=2){
		if(!notPrime[i]){
			for(int j=i*2; j<=n ; j +=i){
				notPrime[j] = true;
			}
		}
	}

	//素数の数
	int count = 0;	
	//素数を足し合わせる
　　　　if(n>=2)　count++;
	for(int i=3; i<=n ; i+=2){
		if(!notPrime[i])　count ++;
	}

	return count ;
}

Math.sqrtがひっかるとこですが、これは「エラトステネスのふるい」という素数判定のアルゴリズムらしいです。

簡単に言うと100までの素数を数えるなら2~10(=Math.sqrt(100))までの倍数を除外すれば素数が見つかるよ、というものです。144までの素数なら2~12までの倍数を除外


あとは偶数は素数にならないので奇数だけでforループ


こんな感じで最初のコードよりも30倍ぐらい早くなりました。わーい