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

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

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

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

わたくし

確認しとくぜ！！

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

素数とは

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

}

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

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

自分でも確認してみて下さいね（　＾ω＾）

因みに、この記事で扱う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);
}