エラトステネスの篩(ふるい) The sieve of Eratosthenes
2006.05.16 00:05 整数
素数の項目で紹介した素数判定プログラムは、与えられた1つの数 x が素数であるか否かを判定するだけでしたが、多くの問題を解く場合、あらかじめ作成された素数表を用いるのが効率的です。
与えられた範囲内の全ての素数を列挙するための高速なアルゴリズムが、エラトステネスの篩(ふるい) The sieve of Eratosthenes です。エラトステネスの篩は、以下の手順で素数表を生成します。ここで、素数表を prime[x] が真ならば x は素数、偽ならば x は合成数(素数ではない整数)であるようなブール型の1次元配列とします。
エラトステネスの篩を実装したプログラム例を以下に示します。
このプログラムは、以下のように多少改良することができます。
与えられた範囲内の全ての素数を列挙するための高速なアルゴリズムが、エラトステネスの篩(ふるい) The sieve of Eratosthenes です。エラトステネスの篩は、以下の手順で素数表を生成します。ここで、素数表を prime[x] が真ならば x は素数、偽ならば x は合成数(素数ではない整数)であるようなブール型の1次元配列とします。
2 以上の整数を列挙しておく | |
最小である 2 を残して、その倍数をすべて消す | |
残った最小の 3 を残して、その倍数をすべて消す | |
残った最小の 5 を残して、その倍数をすべて消す | |
以下同様に、まだ消えていない最小の数を残してその倍数を消すことを繰り返せば、素数だけが残る |
エラトステネスの篩を実装したプログラム例を以下に示します。
001 void eratos ( int n, bool prime[]){ 002 for ( int i = 0; i <= n; i++ ) prime[i] = false; 003 // 奇数を素数の候補とする 004 for ( int i = 3; i <= n; i += 2 ) prime[i] = true; 005 prime[2] = true; 006 int limit = (int)sqrt((double)n) + 1; 007 // 合成数でない奇数だけを残す 008 for ( int i = 3; i <= limit; i += 2 ){ 009 if ( !prime[i] ) continue; 010 // i は素数 i の倍数をすべて消す 011 for ( int j = i + i; j <= n; j += i ) prime[j] = false; 012 } 013 }
このプログラムは、以下のように多少改良することができます。
void eratos ( int n, bool prime[]){ for ( int i = 0; i <= n; i++ ) prime[i] = false; // 奇数を素数の候補とする for ( int i = 3; i <= n; i += 2 ) prime[i] = true; prime[2] = true; int limit = (int)sqrt((double)n) + 1; // 合成数でない奇数だけを残す for ( int i = 3; i <= limit; i += 2 ){ if ( !prime[i] ) continue; for ( int j = i * i, k = i * 2; j <= n; j += k ) prime[j] = false; } }
スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |