【Java】素数を判定して次の素数を見つけるプログラムの作り方

素数とは？

素数とは、1より大きい整数のうち、約数が「1」と「その数自身」の2つだけを持つ数のことです。それ以外の正の約数は一切持ちません。たとえば7は「7 = 1 × 7」としか分解できないため、素数です。

素数判定のアルゴリズム

ある数が素数かどうかを調べるには、以下の手順が基本になります。

• 判定対象の整数を変数Aに代入する。
• Aを2からA−1までの整数で順番に割っていく。
• 途中で一度でも割り切れたら、Aは素数ではない。
• 最後まで割り切れる数が現れなければ、Aは素数である。

なお、実際のプログラムでは「√Aまで調べれば十分」という性質を利用すると処理を大幅に高速化できます。これは、Aがp×qと分解できるとき、pとqの少なくとも一方は必ず√A以下になるためです。

サンプルプログラム

次のJavaプログラムは、ユーザーから整数を1つ受け取り、その数が素数かどうかを判定します。さらに、入力した数より大きい直近の素数（次の素数）も出力します。

import java.util.Scanner;

public class NextNumberisPrime {

    // 素数かどうかを判定するメソッド
    public static boolean isPrime(int num) {
        if (num < 2) {
            return false;
        }
        // 2から√numまで試し割りすれば十分
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    // 次の素数を求めるメソッド
    public static int nextPrime(int num) {
        int candidate = num + 1;
        while (!isPrime(candidate)) {
            candidate++;
        }
        return candidate;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter a number ::");
        int num = sc.nextInt();

        if (isPrime(num)) {
            System.out.println(num + " is a prime number");
        } else {
            System.out.println(num + " is not a prime number");
        }
        System.out.println("Next prime number is: " + nextPrime(num));
    }
}

実行結果

Enter a number ::
25
25 is not a prime number
Next prime number is: 29

コードのポイント

• isPrimeメソッド：引数の数が素数かどうかをboolean型で返します。2未満の数は素数ではないため即座にfalseを返し、試し割りの上限を√numまでに抑えることで無駄な計算を省いています。
• nextPrimeメソッド：入力値に1を加えた数から順に素数判定を行い、最初に素数と判定された数を返します。whileループで候補を1ずつ増やしながら探索するシンプルな構造です。
• mainメソッド：Scannerを使って標準入力から整数を受け取り、判定結果と次の素数を画面に出力します。

まとめ

素数判定は「2から順に割り切れるかを確認する」というシンプルな発想で実装できます。試し割りの範囲を平方根まで絞ると効率が大きく向上する点は押さえておきましょう。「条件を満たすまで候補を進める」nextPrimeの手法は、ほかの探索系の問題にも応用できる便利なパターンです。