C++で素数判定のプログラムを実装する

スポンサーリンク

 

こんにちは!HELLO!您好!привет там ! 안녕하세요 !Hola !

プログラミングを始めて間もない頃に習った懐かしい素数判定のプログラムを作り直してみました。

というのも最近作っていたプログラムの中で急遽必要になりました。

素数判定のアルゴリズムはシンプルで実装しやすいためプログラミング初心者がよく初めに教えられるプログラムです。

結構色々なシーンで何かと使われます。

特に整数問題を扱うプログラムとか。

ということで今日は素数好きにはたまらない一品を作っていこうと思います。それでは早速作っていきましょう。もこみち風

 

素数判定のアルゴリズム

 

まず確認のために、素数とは「1とその数以外に約数をもたない正の整数」であり、1は素数に含めません。

これを踏まえて素数判定のアルゴリズムは以下の通りになります。

正の整数を \(n\) とする。このとき整数 \(n\) を 1から \(\sqrt{n}\) までで繰り返し割り、割り切る整数が存在しない場合、 \(n\) は素数である。

 

これを知らないと愚直なプログラムを書くことになります。

僕は初めて実装したときは律儀に 1から \(n\) までの整数で \(n\) を割って判定していました。

小さな整数を判定する場合は計算量もかかりませんが大きな整数や複数の整数を繰り返し判定する場合は計算量が非常に大きくなってしまいます。

間違いではありませんが効率は悪いです。

「やけに時間がかかるけどこんなもんかぁ。」と思っていたあの頃の自分にキック。

 

それでは僕の実装例をメモしておきます。

これ以外にも実装例はいくつかあるはずですが、とりあえずパッと思いついたものを1つ紹介します。

 

素数判定プログラム

 

実行例 1実行例 2実行例 3

C:\Users\yukiWavy\mycpp>isPrimeNum
Enter integer: 5
Judge: A prime number.

C:\Users\yukiWavy\mycpp>isPrimeNum
Enter integer: 18
Judge: Not a prime number

C:\Users\yukiWavy\mycpp>isPrimeNum
Enter integer: -45
Judge: Not a prime number

 

せっかくですのでこの関数を応用して、指定された範囲の正の整数のなかで素数である整数の個数とその整数を表示する関数を作成しました。

指定範囲内の素数をカウントするプログラム

 

実行例 1実行例 2実行例 3実行例 4

C:\Users\yukiWavy\mycpp>countPrimeNum
From :1
To: 5
Total :3
Prime: 2 3 5

C:\Users\yukiWavy\mycpp>countPrimeNum
From :20
To: 50
Total :7
Prime: 23 29 31 37 41 43 47

C:\Users\yukiWavy\mycpp>countPrimeNum
From :100
To: 200
Total :21
Prime: 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

C:\Users\yukiWavy\mycpp>countPrimeNum
From :200
To: 300
Total :16
Prime: 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293

 

といった具合で簡単に素数をピックアップできますので是非作ってみてください。

ちなみに、素数を単純にピックアップする目的であればもっとシンプルな方法があります。

興味がある方は以下の記事を参考にしてください。

真実のみを記述する会、暗黒通信団 。友達へのプレゼントにどうぞ。控えめに言っても最適。

2018.02.26

 

ではまた!

スポンサーリンク


ABOUT ME!

yuk!

国立大学情報学科に通う大学生です。天然パーマと戦いながらすーぱーエンジニアを目指し技術とセンスを磨いています。 室内に引きこもりがちでヘビメタと猫と甘いものが救いのキーボードカチャカチャ生活ですが、最近はブログで文章を書くことが楽しいです。モットーは「 Who dares wins. = 人生是一箇,活殺全在我。」好きな言葉は「マジ卍」。