C言語

【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と自分自身以外に正の約数を持つか否かを調べる必要があります。

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

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

プログラム作成の手順

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

  1. 判定対象となる数(N)を入力させる
  2. Nに約数(1と自身以外)が存在するかを調べる
  3. 約数の有無によってNが素数か否かを判定する

実装例

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

#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.

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

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

プログラム作成の手順

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

  1. 任意の数(N)を入力させる
  2. 1~Nの範囲内の数に約数が存在するかを順に調べる
  3. 約数の有無によって素数と判定した数のみ表示する

実装例

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

#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,