【Java】配列内の最大素数と最小素数の差を求める方法|エラトステネスの篩で効率的に解く

問題の概要

100万未満の整数要素で構成される配列が与えられたとき、配列内に存在する最大の素数と最小の素数の差を求めます。

実行例

たとえば、次のような配列を考えてみましょう。

配列: [1, 2, 3, 4, 5]

最大の素数 = 5
最小の素数 = 2

差 = 5 - 2 = 3

解決アプローチ:エラトステネスの篩

この問題を効率的に解くには、エラトステネスの篩(Sieve of Eratosthenes)という古典的なアルゴリズムを使用します。これは、ある数値以下のすべての素数を高速に列挙できる手法として知られています。

具体的な手順は以下の通りです。

1. あらかじめ100万以下のすべての素数をエラトステネスの篩で計算しておく
2. 配列の各要素について、素数かどうかをO(1)で判定する
3. 素数の中から最大値と最小値を求める
4. 最大値から最小値を引いた差を返す

Javaでの実装例

以下は、上記のアルゴリズムを実装したJavaプログラムの完全なコードです。

public class JavaTester {

    static int MAX = 1000000;
    static boolean prime[] = new boolean[MAX + 1];

    // エラトステネスの篩を実行するメソッド
    public static void runSieveOfEratosthenes(){
        // すべてのフラグをtrue(素数候補)に初期化
        for(int i=0; i< MAX+1; i++) prime[i] = true;
        // 1は素数ではないため除外
        prime[1] = false;

        for (int p = 2; p * p <= MAX; p++) {
            // prime[p]がtrueのままならpは素数
            if (prime[p]) {
                // pの倍数をすべて素数ではないとマーク
                for (int i = p * 2; i <= MAX; i += p) prime[i] = false;
            }
        }
    }

    // 最大素数と最小素数の差を返すメソッド
    public static int difference(int arr[]){
        int min = MAX + 2;
        int max = -1;
        for (int i = 0; i < arr.length; i++) {
            // 要素が素数かどうかを判定
            if (prime[arr[i]] == true) {
                // 最大値・最小値を更新
                if (arr[i] > max) max = arr[i];
                if (arr[i] < min) min = arr[i];
            }
        }
        return max - min;
    }

    public static void main(String args[]){
        // 篩を事前に実行
        runSieveOfEratosthenes();
        int arr[] = { 1, 2, 3, 4, 5 };
        System.out.println(difference(arr));
    }
}

実行結果

3

処理のポイント

• 前計算による高速化: エラトステネスの篩を一度だけ実行しておけば、以降の素数判定は定数時間で行えます。同じテーブルを使い回せるため、複数のクエリを処理する場合に特に有効です。
• 計算量: 篩の構築には O(N log log N)、配列の走査には O(M)(Mは配列の長さ)しかかからず、非常に効率的です。
• 初期化の工夫: 最小値の初期値を「あり得ない大きな値(MAX + 2)」に、最大値の初期値を「あり得ない小さな値(-1)」に設定することで、どのような配列でも正しく更新できます。