備忘録と戯言

学生がプログラミングの備忘録となんか印象に残ったことを綴る

素数判定について

プログラムを学ぶ際におそらく多くの人は通る道が「素数判定」だと思います。

「100までの素数を求めなさい」とか出題されたことがあるかもしれません。

私もいろいろなサイトを見たり、プログラミングを始めた頃に戻ったつもりになってみました。


おそらく、多くの人は以下のように書くかもしれません。

「※1」

 int main()
 {
     int divisor_num;
     std::vector<int> prime_list;

     for (int i = 1; i <= 100; i++)
     {
         divisor_num = 0;
         for (int s = 1; s <= i; s++)
         {
             if (i % s == 0) divisor_num++;
         }

         if (divisor_num == 2)
             prime_list.push_back(i);
     }

     for (int i = 0; i < prime_list.size(); i++)
         std::cout << prime_list[i] << std::endl;

     std::cout << "全部で" << prime_list.size() << "個です" << std::endl;

     return 0;
 }

という書き方が思い浮かぶ?かもしれません。
思い浮かばなかったらすいません。

しかし、これでは、私でもムダが多いことが一目瞭然です。

ですので少し改良、以下のような書き方にしてみました。

「※2」

 int main()
 {
     int divisor_num;
     std::vector<int> prime_list;

     prime_list.push_back(2);

     for (int i = 3; i <= 100; i += 2)
     {
         divisor_num = 0;
         for (int s = 3; s < i; s += 2)
         {
             if (i % s == 0)
             {
                 divisor_num++;
                 break;
             }
         }

         if (divisor_num == 0)
             prime_list.push_back(i);
     }

     for (int i = 0; i < prime_list.size(); i++)
         std::cout << prime_list[i] << std::endl;

     std::cout << "全部で" << prime_list.size() << "個です" << std::endl;

     return 0;
 }

この書き方の利点としては、「」というのは素数であり、以降の偶数を「素数」でなくします。

ですので、2を最初に追加してしまい、「」から始めます。

ここで、もう、偶数を見る必要はないので、奇数だけを見ます。
そうすると、ループ回数を大幅に減らせますので早くなります。


また、このような書き方もありました。

「※3」

 int main()
 {
     int divisor_num;
     std::vector<int> prime_list;

     prime_list.push_back(2);

     for (int i = 3; i <= 100; i += 2)
     {
         divisor_num = 0;
         for (int s = 3; s < sqrt(i); s += 2)
         {
             if (i % s == 0)
             {
                 divisor_num++;
                 break;
             }
         }

         if (divisor_num == 0)
             prime_list.push_back(i);
     }

     for (int i = 0; i < prime_list.size(); i++)
         std::cout << prime_list[i] << std::endl;

     std::cout << "全部で" << prime_list.size() << "個です" << std::endl;

     return 0;
 }

「※2」と変わったところは、途中のfor文が「for (int s = 3; s < sqrt(i); s += 2)」になったことです。

このようにすると、素数のときにその数の手前まで計算する必要がない」のです。

「※2」だと53を計算するときに3,5,7,・・・49,51まで計算しますが、「※3」だと53の平方根まで(7.2801・・、要は「7」まで)の計算で事足りるのです。

なぜなら、平方根以下の数と、平方根以上の約数は対になるからです。

この3種類で、処理速度を計測してみました。

以下のようなプログラムを書きました

 #include <iostream>
 #include <Windows.h>
 #pragma comment(lib, "winmm.lib")

 #include <vector>

 int main()
 {
     int divisor_num;
     std::vector<int> prime_list;

     DWORD start_time = timeGetTime();

     //----------------------------------------------
     /*ここに「※1」、「※2」、「※3」をブチ込む!*/
     //----------------------------------------------

     DWORD end_time = timeGetTime();
     std::cout << "takes to " << (double)(end_time - start_time) / 1000 << " sec" << std::endl;

     return 0;
 }

ここで、純粋に素数判定だけの処理を計算したいので、途中の「for文ループのネスト」の部分だけを使用します。
素数の個数表示とネスト内にあるvectorの処理は計測外としました。(vector部分は削除しました。)

要は、途中のfor文の処理の開始から終了までの時間を計測してみました。

「結果」

※上限が「1000」の場合

「※1」

takes to 0.009 sec
続行するには何かキーを押してください . . .

「※2」

takes to 0.001 sec
続行するには何かキーを押してください . . .

「※3」

takes to 0 sec
続行するには何かキーを押してください . . .

となりました。

しかし、1000では小さすぎます、露骨に差が出てもらわなくては困るのでもっと大きな値に。

※上限が「1,00,000」の場合

「※1」

takes to 27.227 sec
続行するには何かキーを押してください . . .

「※2」

takes to 2.558 sec
続行するには何かキーを押してください . . .

「※3」

takes to 0.274 sec
続行するには何かキーを押してください . . .

となりました。

以上は全て私の所持しているノートPCで検証結果です。

それぞれの差は歴然としています。

1つの目的に辿り着くだけでも工夫すればあっという間に着いてしまいます。
ここがプログラミングの素晴らしいところですね♪
こういうのを考えたり知ったりするの大好きです♪

ここまで書きましたが、ここで1つ、ツールを作ってみました。

と言ってもただの、「範囲内に素数が何個あって、それはどんな数字か」をファイルに書き出すツールです。

サクッとC#で書いてみました♪
C#楽しい♪
C++の次にだけど・・・

ここにDL用のリンク貼っておきます。

Primality test.zip download←ここから


素数関係の記事なので、素数関係で面白いアルゴリズムがあれば教えてください♪