どうも多浪Fランぼっち底辺大学生です。
C言語初心者学習者が少し頭を抱えてしまう、素数判定と素数の個数を求めるプログラムを書いていきます。
「入力した数字までに含まれる素数の個数はいくつか？」
というプログラムを作りたい！！
けど、・・・・よく分からんわ(´・ω・)
といった悩みを解消しましょうね。
- 任意の数字を素数判定する
- 任意の数字までに含まれる素数の個数を調べる
- 関数を使ってプログラムを書いてみる
上記の項目について知りたい人は読み進めて下さいね( ｀ー´)ノ
それでは見ていきましょう。
Contents
プログラムを書く前に「素数」を認識する
素数とは何か、正の整数nを用いて説明します。
nが素数である条件は1とnの2つの数でしか割り切れないことです。
※なので”１”は自動的に素数ではないことになります。
- 「2」は1と2で割り切れるので”素数”
- 「3」は1と3で割り切れるので”素数”
- 「4」は1と2と4で割り切れるので”素数ではない”
- 「5」は1と5で割り切れるので”素数”
- 「6」は1と2と3と6で割り切れるので”素数ではない”
っと、まぁこんな感じです。
素数判定における考え方
素数判定をする処理には以下の2つの関数が必須です。
- 繰り返し処理（ループ）:for() 又は while()
- 条件分岐 : if()
特定の数ｎが素数であるのかを判定するなら、ｎを{2～(n-1)}で1つずつ割った余りを調べます。
- この間に余りが０になる場合は”素数ではない”
- ”” 余りが０にならない場合は”素数である”
素数判定のソースコードと実行結果
今回は素数判定用の変数flagを用いました。
- 素数ならば：flag=0
- 素数でないならば：flag=1
素数判定のソースコードは以下になります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
#include<stdio.h> int main(){ int n,i; int flag=0; printf("整数を入力してください"); scanf("%d",&n); for (i=2;i<n;i++){ if (n%i==0){ flag=1; } } if (flag==1){ printf("%dは素数ではありません\n",n); } if (flag==0){ printf("%dは素数です\n",n); } } |
そして、実行結果は以下になります。
整数を入力してください：8
8は素数ではありません
整数を入力してください：23
23は素数です
整数を入力してください：100
100は素数ではありません
整数を入力してください：1001
1001は素数ではありません
整数を入力してください：2
2は素数です
特に1001は7で割り切れるので素数ではないす。
自分でも確認してみて下さいね（ ＾ω＾）
因みに、この記事で扱うC言語の素数判定や素数の数を数えるプログラムは、
「新・明解C言語で学ぶアルゴリズムとデータ構造」に記載されているので、購入してみて下さい。
C言語を学ぶ上で買って損は無いですよ！！
nまでの素数の数を求める考え方
素数判定のコードに付け加えをすることで、素数の個数を求めることが出来ます。
- 素数の個数を格納する為の変数countを宣言
- 二重ループにすることで2~(n-1)までの範囲に素数がいくつ存在するか確認
nまでの素数の数を求めるソースコードと実行結果
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include<stdio.h> int main(){ int i,j,n; int flag,count=0; printf("数字を入力してください:"); scanf("%d",&n); for (i=2;i<n;i++){ flag=0; /*判定の初期化*/ for (j=2;j<i;j++){ /*(n-1)までの数の素数判定*/ if (i%j==0){ flag=1; } } if (flag==0){ count+=1; } } printf("%dまでの素数の数は%dです\n",n,count); } |
二重ループにすることでどんな処理が行われるのか以下の表を見てみると分かると思います。
縦の要素”i”が素数であるかどうかの判定で、○なら割り切れる・×なら割り切れないと表しました。
すなわち、○が1つとして無い要素（数）が素数であることになります。
そして、実行結果は以下の様になります。
数字を入力してください：100
100までの素数の数は25です
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個なので正しい結果になりましたね（ ＾ω＾）
自分で関数を作って素数判定する
それでは関数を用いた場合のプログラムについて見て行きましょう。
※（以下のソースコードは、【素数判定】と【素数の個数】を調べるプログラムです）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include<stdio.h> /*プロトタイプ宣言*/ int prime_judge(int num); int get_prime_count(int num); int main(){ int num; //素数判定したい数字 int result; //素数判定の結果 int count; //素数の数 printf("素数判定したい数字を入力 ："); scanf("%d",&num); result=prime_judge(num); count=get_prime_count(num); if (result==1){ printf("入力された数字は素数ではありません\n"); } else{ printf("入力された数字は素数です\n"); } printf("1～%dまでに含まれる素数の個数は %dコ です。\n",num, count); } int prime_judge(int num){ int i; //ループ添え字用 int flag=0; //判定用 for (i=2;i<num;i++){ if (num%i==0){ //割り切れる場合 flag=1; } } return flag; } int get_prime_count(int num){ int i,j; //ループ用添え字 int count=0; //素数の個数 int flag; //素数判定 for (i=2;i<num;i++){ flag=0; for (j=2;j<i;j++){ if (i%j==0){ flag=1; } } if (flag==0){ count+=1; } } return count; } |
このように記述することで、同様な結果が得られます。
素数判定したい数字を入力 ：100
入力された数字は素数ではありません
1～100までに含まれる素数の個数は 25コ です。
素数判定したい数字を入力 ：20
入力された数字は素数ではありません
1～20までに含まれる素数の個数は 8コ です。
素数判定したい数字を入力 ：101
入力された数字は素数です
1～101までに含まれる素数の個数は 25コ です。
プロトタイプ宣言した関数は prime_judge(int num) と get_prime_count(int num)の2つです。
prime_judge(int num)では、素数であるかの判定を行います。
get_prime_count(int num)では、引数の値までに含まれる素数の個数をカウントしていますね。
もし、関数に関する知識が分からないのであれば以下の参考書を手に取って学習してみて下さい。
かな～り分かりやすいですよ(‘ω’)ノ
まとめ
プログラムを記述する以前に素数の性質を理解する必要がある。
また、二重ループなどの処理に慣れないのなら表や数式を書いてみて理解を深めましょう。
以上です。
新・明解C言語で学ぶアルゴリズムとデータ構造 (明解シリーズ)
