目次に戻る


このエントリーをはてなブックマークに追加


素数判定

素数(Prime Number)とは、その数自信と1しか約数を持たない数字。
2,3,5,7,11,13,17,19,23...みたいな。


今回はこの素数を判定するプログラムを作っていこうと思う!!

大丈夫、難しくはない。そして今まで学んだ for と if、while などで簡単に作れちゃう。

判定方法は2種類あって、どちらも解説していくのでご安心を。




簡単な素数判定

先ほど言ったように素数っていうのは、その数と1でしか割り切れないわけ。

つまり「ある数字 x に対して、2から(x-1)までの数字を順に割って、途中で割り切れてしまったら合成数、割り切れずに(x-1)までたどり着いたら素数ってこと。

案外簡単に思えてくるよね。
こういったプログラムを1から書くときは処理の流れを予め書いておくとコーディングしやすい。

今回の素数判定は

①ユーザーの入力
②もし入力した数字 x が
 {1以下なら①に戻る}
 {2以上なら③へ}
③入力した数字 x に対して i = 2,3,4,...,(x-1)として x%i を求めていく。
 {x%i == 0 なら合成数。計算終了}
④③で計算終了しなかったら素数。


この順序で言葉通りの処理をコーディングしていくだけ!

まずは自分で考えてコーディングしてみてほしい
コーディング例はここから少し下に載せてあるので、参考に!


スポンサーリンク

















以下は僕の作ったコーディング例
                    /*
                     *単純な素数判定プログラム prime_1.cpp
                     */

                    #include<iostrem>
                    using namespace std;

                    int main(){

                      int num = 0;

                      do { //①
                        cout << "素数判定します。2以上の整数を入力 : ";

                        cin >> num;

                        if( num <= 1 ) //②
                          cout << "2以上の整数を入力してください。" << endl;

                      }while( num <= 1 );

                      if( num == 2 )
                        cout << num << "は素数です。" << endl;
                        return 0;
                      }

                      for( int i = 2; i < num; i++){ //③
                        if( num % i == 0 ){
                          cout << num << "は素数ではありません。" << endl;
                          return 0;
                        }
                      }

                      cout << num << "は素数です。" << endl; //④


                      return 0;

                    }

                

cppファイルは こちら から。

解かり易く上記の処理の数字をコメントアウトしておいた。
どうだろうか、問題なく実行できただろうか。
do while文を使っているけどwhile文でも大丈夫そう。

また、2が入力されたときはそもそもfor文に入らないので素数判定となる。


しかし、もし大きな素数を入力したらめちゃくちゃ時間かかりそうじゃない??
ちなみに、2147483647っていうそこそこ大きな素数を入力してみると...

僕のPCでは28.508秒でした。
ちなみに上のソースファイルには時間計測できるようにコーディングしてあるから遊んでみてね。




計算速度を上げた素数判定

今度はさっき課題になった計算時間をどうにか短くする素数判定を考えてみる。

まず偶数って2以外すべて偶数なので、偶数を振るい落として無駄な計算を減らす。
これで単純計算で半分になりそうだね。


そして素数の性質を確認し直す。
調べてみると、ある自然数 x において、√x 以下の奇数と互いに素であれば、x は素数である。

おお..? なるほど、つまりさっきの簡単な素数判定のループ条件を変えれば良いだけぽいな。

でさっきは繰り返しする度にインクリメントしていたけど、奇数だけでいいので、2ずつ増やしていく。

そうすると...

                        /*
                         *計算速度を上げた素数判定プログラム prime_2.cpp
                         */

                        #include<iostream>
                        #include<math.h>
                        using namespace std;

                        int main(){

                          int num = 0;

                          do {
                            cout << "素数判定します。2以上の整数を入力 : ";

                            cin >> num;

                            if( num <= 1 )
                              cout << "2以上の整数を入力してください。" << endl;

                          }while( num <= 1 );

                          //以下変更

                          if( num == 2 ){
                            cout << num << "は素数です" << endl;
                            return 0;
                          }

                          //①ここで偶数を振るい落とす
                          if( num % 2 == 0){
                            cout << num << "は素数ではありません。" << endl;
                            return 0;
                          }

                          //②奇数のみ、かつ√num以下のみの計算
                          int i = 3;
                          while( i <= sqrt(num) ){ // sqrt()はmath.hライブラリの2乗根計算してくれる関数
                            if( num % i == 0 ){
                              cout << num << "は素数ではありません。" << endl;
                              return 0;
                            }
                            i += 2;
                          }

                          cout << num << "は素数です。" << endl;


                          return 0;

                        }

                    

こんなかんじだろうか。
ファイルは こちら から。


ちなみに平方根を計算してくれるsqrt()は math.h をインクルードする必要がある。
このプログラムで先ほどの2147483647を入力してみると...、0.032秒に抑えることができた!!

このように実行時間を考慮したプログラミングができる、というのは大事なことなのです!!




さて次回は、 7, 関数ってなんだろう…?【void function(){...}】



スポンサーリンク






このエントリーをはてなブックマークに追加