【C言語】素数の判定 / 表示を行う

プログラミング初心者向けの練習問題として以下のようなものがあります。

本記事では、これら処理を実装する方法について説明します。

そもそも「素数」とは？

まずは素数とは何かについて簡単に説明します。

素数の定義

素数とは、1と自分自身以外に正の約数を持たない自然数（1以外）のことです。

素数の例をいくつか示します。

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 …

2は1と2以外に正の約数を持たないため素数、3も1と3以外に正の約数を持たないため素数ですが、4は1と4以外に2を約数に持っているため素数ではありません。

素数の求め方

現状、素数を求めるための完璧な方程式は発見されていません。

そのため、素数を求めるには対象の数字が1と自分自身以外に正の約数を持つか否かを調べる必要があります。

①「素数の判定プログラム」を作成する

ここでは「対象の数字が素数か否かを判定する」プログラムを作成します。

プログラム作成の手順

プログラム作成の手順は以下の通りです。

実装例

上記の手順に従ってプログラムを作成します。

#include <stdio.h>

int main(void) {

  /* 変数を定義する */
  int number, i;

  /* 数値の入力を促すメッセージを表示 */
  printf("Enter a number : \n");
  scanf("%d", &number);
  printf("\n");

  /* 入力した数値に約数（1と自身以外）が存在するかを調べる */
  for(i=2; i<number; i++){
    if(number%i==0){
      break;
    }
  }

  /* 入力した数値が素数か否かを判定する */
  if(i==number){
    printf("%d is a prime number.\n", number);
  }else{
    printf("%d is NOT a prime number.\n", number);
  }

  return 0;
}

このプログラムを実行すると以下の出力結果が得られます。

Enter a number : 
3

3 is a prime number.

…

Enter a number : 
4

4 is NOT a prime number.

②「素数の表示プログラム」を作成する

ここでは「指定した範囲内の素数の一覧を表示する」プログラムを作成します。

プログラム作成の手順

プログラム作成の手順は以下の通りです。

実装例

上記の手順に従ってプログラムを作成します。

#include <stdio.h>

int main(void) {

  /* 変数を定義する */
  int number, i, j;

  /* 数値の入力を促すメッセージを表示 */
  printf("Enter a number : \n");
  scanf("%d", &number);
  printf("\n");

  /* 指定した範囲内の数値に約数（1と自身以外）が存在するかを順に調べる */
  for(i=2; i<number; i++){
    for(j=2; j<i; j++){
      if(i%j==0){
        break;
      }
    }
    if(i==j){
      printf("%d, ", i);
    }
  }

  return 0;
}

このプログラムを実行すると以下の出力結果が得られます。

Enter a number : 
50

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 

おすすめの記事

本記事を読まれた方には、以下の記事もおすすめします。

【中・上級者への道！】C言語の次に勉強するべきプログラミング言語は何？【オススメは○○】