エラトステネスのふるい(素数判定) - 秋田大学ICPC対策室@wiki

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

素数表を生成するアルゴリズムにエラトステネスのふるいというものがあります。

まずはこのアルゴリズムなしで素数かどうか調べる方法を考えてみます。
ある数が素数かどうか調べるにはその数がその数より小さい数すべて(1以外)で
割り切れない場合素数なのでfor文で回せば簡単にコーディングできそうです。

プログラム例

/*入力した値が素数かどうか識別するプログラム*/
#include <iostream>
using namespace std;

int main(){
	int n;
	while( cin >> n , n ){
		bool flag = true; 
		//1は素数でない
		if( n == 1 ) flag = false;

		//nを2から(n-1)まで割って割り切れるか調べる
		for (int i=2 ; i < n ; i++ ){
			if ( n % i == 0 ){ //割り切れたら素数でない
				flag = false;
				break;
			}
		}
		if( flag )
			cout << "数値は素数です" << endl;
		else
			cout << "数値は素数ではありません" << endl;
	}
}

この方法では大きな数に対して素数判定をすると非常に時間がかかります。
エラトステネスのふるいという方法は先程よりも効率がよく10^6程度の数であれば高速に素数判定ができます。
wikidediaのエラトステネスの篩に詳しい説明があるのでここでは説明しません。
以下がプログラム例です。

/*1000000以下の素数で入力したn以下の素数をすべて出力するプログラム*/
#include <iostream>
#include <cmath>
const int MAX = 1000001;
using namespace std;

bool p[MAX];

void sieve_of_eratosthenes(){
    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;
            }
        }
    }
}

int main(){
    int n;

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

...