エラトステネスのふるい(素数判定)
素数表を生成するアルゴリズムにエラトステネスのふるいというものがあります。
まずはこのアルゴリズムなしで素数かどうか調べる方法を考えてみます。
ある数が素数かどうか調べるにはその数がその数より小さい数すべて(1以外)で
割り切れない場合素数なのでfor文で回せば簡単にコーディングできそうです。
ある数が素数かどうか調べるにはその数がその数より小さい数すべて(1以外)で
割り切れない場合素数なのでfor文で回せば簡単にコーディングできそうです。
+ | プログラム例 |
この方法では大きな数に対して素数判定をすると非常に時間がかかります。
エラトステネスのふるいという方法は先程よりも効率がよく10^6程度の数であれば高速に素数判定ができます。
wikidediaのエラトステネスの篩に詳しい説明があるのでここでは説明しません。
以下がプログラム例です。
エラトステネスのふるいという方法は先程よりも効率がよく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; } } } }
...