Javaで2つの区間の間にある素数を表示するプログラム

この記事では、指定した2つの区間(範囲)の間にある素数を表示するJavaプログラムの作成方法について解説します。素数とは、1とその数自身の2つだけを約数に持ち、それ以外のどの数でも割り切ることのできない特別な数です。

ある数が素数であるのは、その約数が1とその数自身だけである場合です。たとえば11は素数であり、その約数は1と11のみです。素数の例としては、2、3、5、7、11、13などが挙げられます。なお、2は唯一の偶数の素数であり、それ以外の素数はすべて奇数になります。

実行例

以下に入力と出力の例を示します。

入力

入力値が次のとおりであるとします。

開始番号 : 1
終了番号 : 75

出力

期待される出力は次のとおりです。

区間1から75までの素数は次のとおりです:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73

アルゴリズム

ステップ1 - 開始
ステップ2 - 必要な変数を宣言する
ステップ3 - ユーザーから値を入力する、または値を定義する
ステップ4 - 下限値から上限値までの間でwhileループを実行する
ステップ5 - forループで区間内の各数値を順に調べ、1以外のより小さい数で割り切れるかどうかを確認し、結果を保持する
ステップ6 - 結果を表示する
ステップ7 - 終了

例1:ユーザーから入力を受け取る場合

この例では、Scannerクラスを使ってプロンプト経由でユーザーの入力を受け付けます。オンラインのJava実行環境(コーディンググラウンド)などでも実際に動作を試すことができます。

import java.util.Scanner;
public class PrimeNumber {
   public static void main(String[] args) {
      int my_high, my_low, i;
      boolean my_temp;
      System.out.println("Required packages have been imported");
      Scanner my_scanner = new Scanner(System.in);
      System.out.println("A reader object has been defined ");
      System.out.print("Enter the starting number : ");
      my_low = my_scanner.nextInt();
      System.out.print("Enter an ending Number: ");
      my_high = my_scanner.nextInt();
      System.out.println("The prime numbers between the interval " + my_low + " and " + my_high + " are:");
      while (my_low < my_high) {
         my_temp = false;
         for(i = 2; i <= my_low/2; ++i) {
            if(my_low % i == 0) {
               my_temp = true;
               break;
            }
         }
         if (!my_temp && my_low != 0 && my_low != 1)
            System.out.print(my_low + " ");
         ++my_low;
      }
   }
}

出力

Required packages have been imported
A reader object has been defined
Enter the starting number : 1
Enter the ending number : 75
The prime numbers between the interval 1 and 75 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73

例2:値を事前に定義する場合

この例では、整数値があらかじめ定義されており、その値を取得してコンソールに表示します。入力処理が不要になるため、ロジックの動作確認に便利です。

public class PrimeNumber {
   public static void main(String[] args) {
      int my_high, my_low, i;
      boolean my_temp;
      my_low = 1;
      my_high = 75;
      System.out.println("The starting and ending numbers are defined as " + my_low + " and " + my_high);
      System.out.println("The prime numbers between the interval " + my_low + " and " + my_high + " are:");
      while (my_low < my_high) {
         my_temp = false;
         for(i = 2; i <= my_low/2; ++i) {
            if(my_low % i == 0) {
               my_temp = true;
               break;
            }
         }
         if (!my_temp && my_low != 0 && my_low != 1)
            System.out.print(my_low + " ");
         ++my_low;
      }
   }
}

出力

The starting and ending numbers are defined as 1 and 75
The prime numbers between the interval 1 and 75 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73

プログラムのポイント

素数判定の仕組み

このプログラムでは、各数値に対して2から「その数の半分」までの整数で順番に割り算を行い、1つでも割り切れる数があれば素数ではないと判断しています。割り切れる数が見つかった時点でboolean型のフラグ(my_temp)をtrueにし、breakでループを抜けることで無駄な計算を省いています。

0と1の扱い

0と1は定義上素数ではないため、my_low != 0 && my_low != 1という条件で除外しています。そのため、開始番号が1であっても出力される最小の素数は2になります。

効率をさらに高めるには

より大きな範囲を扱う場合は、割る数の上限を「その数の半分」ではなく「その数の平方根(√n)」までにすると、判定回数を大幅に減らせます。また、エラトステネスのふるいなどのアルゴリズムを使えば、広い範囲の素数をさらに高速に求めることも可能です。