「エラトステネスのふるい(素数判定)」の編集履歴(バックアップ)一覧はこちら
「エラトステネスのふるい(素数判定)」(2012/02/09 (木) 17:12:48) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
**エラトステネスのふるい(素数判定)
素数表を生成するアルゴリズムにエラトステネスのふるいというものがあります。
まずはこのアルゴリズムなしで素数かどうか調べる方法を考えてみます。
ある数が素数かどうか調べるにはその数がその数より小さい数すべて(1以外)で
割り切れない場合素数なのでfor文で回せば簡単にコーディングできそうです。
#region(close, プログラム例)
/*入力した値が素数かどうか識別するプログラム*/
#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;
}
}
#endregion
次ににエラトステネスのふるいをコーディングします。
wikidediaの[[エラトステネスの篩>>http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9]]に詳しい説明があるのでここでは説明しません。
以下がプログラム例です。
/*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;
}
}
}
}
...
**エラトステネスのふるい(素数判定)
素数表を生成するアルゴリズムにエラトステネスのふるいというものがあります。
まずはこのアルゴリズムなしで素数かどうか調べる方法を考えてみます。
ある数が素数かどうか調べるにはその数がその数より小さい数すべて(1以外)で
割り切れない場合素数なのでfor文で回せば簡単にコーディングできそうです。
#region(close, プログラム例)
/*入力した値が素数かどうか識別するプログラム*/
#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;
}
}
#endregion
この方法では大きな数に対して素数判定をすると非常に時間がかかります。
エラトステネスのふるいという方法は先程よりも効率がよく10^6程度の数であれば高速に素数判定ができます。
wikidediaの[[エラトステネスの篩>>http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9]]に詳しい説明があるのでここでは説明しません。
以下がプログラム例です。
/*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;
}
}
}
}
...
表示オプション
横に並べて表示:
変化行の前後のみ表示: