プログラミング

【大学の課題で出るC言語】素数判定と素数の数を求める

大学の課題で出るC言語。素数判定と素数の個数

どうも多浪Fランぼっち底辺大学生です。

C言語初心者学習者が少し頭を抱えてしまう、素数判定素数の個数を求めるプログラムを書いていきます。

今回の記事はプロトタイプ宣言による関数を使用しない方法でやっていきたいと思います。

わたくし
わたくし
確認しとくぜ!!

関数を利用するソースコード例を見たい方は以下の記事をご覧ください。

それでは見ていきましょう。

素数とは

素数とは何か、正の整数nを用いて説明します。

nが素数である条件は1とnの2つの数でしか割り切れないことです。

※なので”1”は自動的に素数ではないことになります。

  • 2は1と2で割り切れるので”素数”
  • 3は1と3で割り切れるので”素数”
  • 4は1と2と4で割り切れるので”素数ではない”
  • 5は1と5で割り切れるので”素数”
  • 6は1と2と3と6で割り切れるので”素数ではない”

っと、まぁこんな感じです。



素数判定における考え方

素数判定をする処理には以下の2つの関数が必須です。

  1. 繰り返し処理(ループ):for() 、while()
  2. 条件分岐 : if()

 特定の数nが素数であるのかを判定するなら、nを{2~(n-1)}で1つずつ割った余りを調べます。

  • この間に余りが0になる場合は”素数ではない”
  •   ”” 余りが0にならない場合は”素数である”

素数判定のソースコードと実行結果

今回は素数判定用の変数flagを用いました。

  • 素数ならば:flag=0
  • 素数でないならば:flag=1

素数判定のソースコードは以下になります。

そして、実行結果は以下になります。

素数判定の実行結果

特に1001は7で割り切れるので素数ではないす。

自分でも確認してみて下さいね( ^ω^)

因みに、この記事で扱うC言語の素数判定や素数の数を数えるプログラムは、

新・明解C言語で学ぶアルゴリズムとデータ構造」に記載されているので、購入してみて下さい。

nまでの素数の数を求める考え方

素数判定のコードに付け加えをすることで、素数の個数を求めることが出来ます。

  • 素数の個数を格納する為の変数countを宣言
  • 二重ループにすることで2~(n-1)までの範囲に素数がいくつ存在するか確認

nまでの素数の数を求めるソースコードと実行結果

二重ループにすることでどんな処理が行われるのか以下の表を見てみると分かると思います。

二重ループの処理

縦の要素”i”が素数であるかどうかの判定で、○なら割り切れる・×なら割り切れないと表しました。

すなわち、○が1つとして無い要素(数)が素数であることになります。

 

そして、実行結果は以下の様になります。

素数の個数の実行結果

100までの素数は(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97)の計25個なので正しい結果になりましたね( ^ω^)

プログラミングの参考書
【大学生の課題で出るC言語】持っておくべきおすすめの参考書どうも多浪Fランぼっち底辺大学生です。 今回はC言語プログラミングを履修している大学生におすすめの参考書の紹介をします。 ...

まとめ

まとめ

プログラムを記述する以前に素数の性質を理解する必要がある。

また、二重ループなどの処理に慣れないのなら表や数式を書いてみて理解を深めましょう。

人気ブログランキング
関連記事