Javaで1からNまでのすべての素数を表示するプログラムの書き方

この記事では、Javaを使って1からNまでのすべての素数を表示する方法を解説します。1から無限大までの正の整数は「自然数」と呼ばれます。その中でも素数とは、1とその数自身だけを約数（因数）に持ち、それ以外のどの数でも割り切れない特別な数のことです。

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

以下に具体的な実行例を示します。

入力

入力値が次のようになっているとします。

Enter the value of n :10

出力

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

2 3 5 7

アルゴリズム

ステップ1：開始
ステップ2：整数型変数 n を宣言する
ステップ3：ユーザーに整数値の入力を促す、または値を直接コードに記述する
ステップ4：値を読み込む
ステップ5：2からnまでの各数値 j について、1から j までの数で割り切れる回数をカウントする
ステップ6：割り切れる場合はカウンターを増やし、次の数を確認する
ステップ7：カウンターが2（1と自分自身のみで割り切れる）の場合、その数を素数として記録する
ステップ8：素数として判定された数値を表示する
ステップ9：終了

例1：ユーザーからの入力を使用する場合

ここでは、Scannerクラスを使ってユーザーが入力した値をもとに処理を行います。オンラインの実行環境などでも実際に動作を確認できます。

import java.util.Scanner;
public class PrimeNumbers{
    public static void main(String arg[]){
        int i,n,counter, j;
        Scanner scanner = new Scanner(System.in);
        System.out.println("Required packages have been imported");
        System.out.println("A reader object has been defined ");
        System.out.print("Enter the n value : ");
        n=scanner.nextInt();
        System.out.print("Prime numbers between 1 to 10 are ");
        for(j=2;j<=n;j++){
            counter=0;
            for(i=1;i<=j;i++){
                if(j%i==0){
                    counter++;
                }
            }
            if(counter==2)
            System.out.print(j+" ");
        }
   }
}

出力

Required packages have been imported
A reader object has been defined
Enter the n value : 10
Prime numbers between 1 to 10 are 2 3 5 7

例2：値をあらかじめ定義しておく場合

ここでは、整数値が事前にコード内で定義されており、その値にアクセスしてコンソールに表示します。

public class PrimeNumbers{
    public static void main(String arg[]){
        int i,n,counter, j;
        n= 10;
        System.out.printf("Enter the n value is %d ", n);
        System.out.printf("\nPrime numbers between 1 to %d are ", n);
        for(j=2;j<=n;j++){
            counter=0;
            for(i=1;i<=j;i++){
                if(j%i==0){
                    counter++;
                }
            }
           if(counter==2)
         System.out.print(j+" ");
      }
   }
}

出力

Enter the n value is 10
Prime numbers between 1 to 10 are 2 3 5 7

コードの仕組みとポイント

このプログラムでは、外側のループで2からnまでの各数値を順番に取り上げ、内側のループで1からその数自身までの範囲で割り切れる回数をカウントしています。割り切れる回数がちょうど2回（1と自分自身）であれば、その数は素数であると判断できます。

なお、この方法はシンプルで理解しやすい反面、計算量はO(n²)となります。より大きな数を扱う場合は、約数の確認範囲を√jまでに絞る、またはエラトステネスの篩（ふるい）などのアルゴリズムを利用することで、効率を大幅に向上させることができます。