某所で素数を列挙するプログラムを見かけて、自分も作ってみようという気になりました。また、ついでに C言語、C++、C# でも同じように作成して、そのコードの違いや実行速度の差を検証もしてみました。私の当初の予定では、圧倒的に C++ が高速だと思ってました。さて、その結果はどうなったでしょうか。

  • アルゴリズム
素数とは、1と自分自身で割り切れない自然数と定義されています。1は素数ではないです。自分自身が1なので、2通りの値で割ることが出来ないためです。さて、これを単純にプログラムに置き換えていくと、n の値が素数かどうかを調べるために 2 から n-1 までを順次割っていって、割り切れたら素数ではないという判定をします。ですが、これはとても非効率な考え方です。理由は、例えば 2 で割り切れたら 4 で割れるかどうかを考えるまでもなく割り切れるためです。

つまり、1から順番に計算した場合は、今まで素数と判定できた値で除算して試せば、他の数字は確認する必要がないですよね。そのため、今まで出てきた素数をまとめてどこかに覚えておくことが必要です。そこで使うのがリスト構造です。リスト構造は、総数が分からない集合体を作っていくのにとても都合が良いのです。リスト構造は別途解説していますので、詳しくは以下を参照してください。




指定の値で割り切れるかどうかです。例えば 3 で割り切れるかどうかだと、n / 3 * 3 の結果が元の値に戻れば、それは割り切れていると判断できます。整数型の場合は、割り算の結果、小数点以下が発生した際は切り捨てられますから、同じ値を掛けても元の値に戻りません。この性質を利用します。

  • C言語での実装
C言語の実装例を下記に提示します。
Cリスト関連定義
C言語にはリスト構造を処理する関数が用意されていないので、自分で処理系を用意する必要があります。リスト構造で1つのユニットに必要なのは、値と次のユニット位置を示すポインタです。そこで、最初に構造体でユニットを定義しています。また、ユニットを取り出す専用の GetUnit という関数も用意しました。
C判定メイン処理
プログラム全体は言語に関わらず全て同様としています。最初に調査の最大数入力して、その数字までを 2 から順番に調査して、素数であれば画面に表示します。最後に見つかった素数の数を表示しています。なお、処理時間も表示するようにはしていますが、これは後述する実行速度比較のための仕掛けで、素数判定には何も関係ありません。
ロゴス(LOGOS) 保冷剤 氷点下パック GTマイナス16度 ハード 900 長時間 防災 日本製

【Amazon】
ロゴス(LOGOS) 保冷剤 氷点下パック GTマイナス16度 ハード 900 長時間 防災 日本製
ロゴス(LOGOS)
2012-03-16
※ マジでよく冷えます。夏場のゴルフの必需品になりました。
  • C++での実装
Cとよく似ているC++ですが、stdテンプレート関数がとても便利で、当然のようにリストも用意されています。その中で今回は Vector を利用することにしました。理由は高速動作が期待できるためです。プログラムは以下の通りとなりました。
C++判定メイン処理
Cのプログラムと比較するとかなりシンプルですよね。クラスを使わずとも、ここまで可読性が良くなるのがC++の魅力でもあります。コード内に clock の値を読み込む箇所がありますが、ここは実行速度計測に使っていますので、素数判定には影響ありません。

  • C#での実装
最後にC#です。便利な命令が揃っていて、こんな事が出来ないかなって調べると、だいたい出来てしまう気がするぐらい、各種命令が豊富に揃っています。リスト構造も当然用意されていて、使用用途に合わせて、様々な形式のリストを選ぶ事が出来ます。今回は順次参照という単純な使い方でしたので、最も一般的な List を使用することにしました。コードは以下のとおりです。
C#判定メイン処理
こちらもシンプルです。パッと見では殆ど違いがわからないぐらい近いです。処理の流れに関しては、上記と全く同様です。時間計測は C# に用意されている Stopwatch を使用しています。

  • 処理速度の比較
コンソール画面に見つかった素数を表示していますが、この表示があると処理時間の比較が出来ないため、時間計測時は表示を OFF にしています。実行時、最大数に 1000000（百万）を入力して、5回の時間計測結果は以下のとおりです。

C++　4.147sec　4.143sec　4.130sec　 4.144sec　4.165sec　
C#4.157sec4.191sec4.171sec4.201sec4.208sec
C8.744sec8.852sec8.771sec8.837sec8.697sec

いずれもリリースビルドで、プログラム内で clock または Stopwatch で計測した値を提示しています。内藤的には意外な結果になってます。予想以上に C# が速いです。これはまあ、自分が現状で最も多用しているコンパイラなので、速度が出る記述方法をある程度理解しているためとも言えます。

C# は他にはデバッグビルドとリリースビルドでびっくりするぐらい実行速度が異なりました。試しにデバッグビルドで実行すると、こんな処理時間となります。

C++　7.692sec　7.604sec　7.711sec　7.699sec　7.741sec　

ここまで遅くなると不気味なぐらいですね…。あと、C言語が予想外に遅かったです。これは malloc による動的メモリ確保が遅いのだと予想しています。他の言語はメモリ確保はシステム側に任せてますので、無駄がないのではないかと。ゲーム制作の現場だと、ちまちまメモリ確保は断片化の原因になるので、まとめてどかんと確保して、自分でメモリの割り当てを管理していました。正直面倒でした…
総括ですが、以前は遅いと言われていた C# がここまで速度改善が出来ているとは思いませんでした。正直、もう少し遅いと思っていました。ただ、今回はプログラムサイズ的には小さかったため、もしかしたら CPU キャッシュに収まったから速かっただけなのかもしれません。そう考えるとデバッグビルドで遅いのは、キャッシュから外れてるため…とも言えます。まあ、想像なので何が正しいのかは分かりませんが、何かの参考になれば幸いです。
ロゴス(LOGOS) 氷点下キープシリンダー・サーモテクト 81287610

【Amazon】
ロゴス(LOGOS) 氷点下キープシリンダー・サーモテクト 81287610
ロゴス(LOGOS)
2018-08-01

ロゴス 保冷剤 氷点下パックGT-16℃・コンパクト(2pcs) 81660609

【Amazon】
ロゴス 保冷剤 氷点下パックGT-16℃・コンパクト(2pcs) 81660609
ロゴス(LOGOS)
※ ドリンクを冷やして持ち運ぶならこの組み合わせが最強です。朝、ゴルフ場に出掛けて、昼、飲んでもキンキンに冷えてます…というか、一部内容物が凍ってました。凄いです。
今回提示したプログラムのサンプルをダウンロードできるようにしておきました。興味があればご参照ください。

PrimeSrcSample.zip
20240704-1800

※ 20240705-1120追記
C の動作速度が遅いのは malloc だと確信があり、また X（Twitter）でも指摘がありましたので、毎回メモリ確保を取りやめて、最初に丸ごと動的配列確保として実行させてみました。その結果は、

C (動的配列)　4.073sec　4.104sec　4.118sec　4.143sec　4.136sec　

結果、C が一番現時点で高速に動作していることが分かります。まー、ただここまで来ると誤差範囲ではありますよねぇ。以下が実行に使用したプログラムです。
C（動的配列版）

タグ ：
#素数
#アルゴリズム
#C言語
#C#
#C++