C言語で素数を列挙するプログラム

少し前にC言語のおさらいをしようと思い、素数を求めるプログラムを書いてみました。素数とは１とその数だけでしか割り切れない数のこと。数学の内容なのでさすがに奥が深く、色々な素数判定アルゴリズムあるみたいですね。

参考書は、昔からあるロングセラー「新版明解C言語(著者:柴田望洋氏)」を今回使いました。実際読んでみると、サンプルが多いので、プログラム経験者ならわかりやすいと感じてます。本書の５章に素数を求めるプログラムのコードがあり、それを応用して書いたのが後述のコード"prime.c"です。

概要

今回作成したprime.cの処理の概要はこんな感じです。

列挙したい素数の件数を引数で指定
素数の判定
表示処理

出来上がったコードをコンパイルしてプログラムは完成します。それでは簡単に解説していきます。

引数を使えるように

今回は列挙したい素数の件数を引数でプログラムに渡せるようにし、引数なしのときはデフォルトで100万件の素数を列挙するようにしました。引数の範囲は2-1000万件としています。(11-24行目)

素数判定

このプログラムでは試し割り方を用いていて、

2と3は必ず素数
偶数は素数ではないので奇数だけを判定対象
対象が平方根以下の全ての素数で割り切れなければその数は素数

と判定しています。コードでは36-49行目がその処理にあたります。

表示処理

画面に素数を列挙する処理(51-60行目)に加え、判定処理の時間と表示処理の時間を出しています。ちなみにウチのMacBook Air 11 Mid 2013 i5 ではこんな感じで6秒ちょいで計算、2秒弱で表示してます。

calc elapsed time = 6.182908
view elapsed time = 1.993083

異なるパソコンで同じソースコードを使えば簡易的なベンチマークとしても使えますね。コードを改良して高速化を図るのもホビープログラミングとして楽しめます。頭の体操的な使い方にもなるかも^^

gccでコンパイル

Macのターミナルでコンパイルする方法をざっくりと示すと、gcc -o prime.exe prime.c -O2とコマンドを打つと同一ディレクトリにprime.exeファイルが生成されます。そのままターミナルで./prime.exeと叩けば実行できますよ。
あと、Macでgccを使うには、Xcode Command Line Toolsがインストールされている必要があります。

まとめ

異なるパソコンで同じソースコードを使えば簡易的なベンチマークとしても使えますね。コードを改良して高速化を図るのもホビープログラミングとして楽しめます。頭の体操的な使い方にもなるかも^^
(突き詰めると既に高速なアルゴリズムがあったりするんですがｗ) プログラミングを始めてみたい人とかにも、何か取っ掛かりになるようなものがあるといいですね。