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

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

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

「入力した数字が素数か？」
「入力した数字までに含まれる素数の個数はいくつか？」
というプログラムを作りたい！！

けど、・・・・よく分からんわ(´・ω・)

といった悩みを解消しましょうね。

この記事の内容

任意の数字を素数判定する
任意の数字までに含まれる素数の個数を調べる
関数を使ってプログラムを書いてみる

上記の項目について知りたい人は読み進めて下さいね( ｀ー´)ノ

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

Contents

プログラムを書く前に「素数」を認識する
素数判定における考え方
- 素数判定のソースコードと実行結果
nまでの素数の数を求める考え方
- nまでの素数の数を求めるソースコードと実行結果
自分で関数を作って素数判定する
まとめ

プログラムを書く前に「素数」を認識する

素数とは何か、正の整数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

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

#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);
  }
}

#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までの素数の数を求めるソースコードと実行結果

#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);
}

#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個なので正しい結果になりましたね（　＾ω＾）

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

自分で関数を作って素数判定する

それでは関数を用いた場合のプログラムについて見て行きましょう。

※（以下のソースコードは、【素数判定】と【素数の個数】を調べるプログラムです）

#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;
}