【C++】指定した範囲内の素数の最大差を求めるクエリ問題の解法

この記事では、2つの値 L と R から構成される Q 個のクエリが与えられたとき、それぞれの範囲内に存在する素数のうち「最大の素数」と「最小の素数」の差（最大差）を求めるプログラムを C++ で実装する方法を解説します。

問題の概要

各クエリには2つの整数 L と R が与えられます。私たちのタスクは、区間 [L, R] 内に存在する素数を調べ、その中で最大の素数と最小の素数の差を計算することです。なお、範囲内に素数が1つも存在しない場合は 0 を出力します。

具体例を使って問題を理解しましょう。

入力

Q = 3
4 15
32 37
54 1100

出力

For query 1: The maximum difference between primes numbers is 8
For query 2: The maximum difference between primes numbers is 0
For query 3: The maximum difference between primes numbers is 1038

解説

クエリ1： 区間 [4, 15] 内の最小の素数は 5、最大の素数は 13 です。したがって差は 13 − 5 = 8 となります。

クエリ2： 区間 [32, 37] 内に存在する素数は 37 のみです。最小値と最大値が同じ素数になるため、差は 0 となります。

クエリ3： 区間 [54, 1100] 内の最小の素数は 59、最大の素数は 1097 です。したがって差は 1097 − 59 = 1038 となります。

解法のアプローチ

この問題を効率的に解くためには、あらかじめ素数表を作成しておくのが有効です。手順は以下の通りです。

1. エラトステネスの篩（ふるい）を用いて、上限値（ここでは 100005）までの素数表を事前に作成します。
2. 各クエリに対して、L 以上で最初に見つかる素数（範囲内の最小の素数）を前方から探索します。
3. 同様に、R 以下で最初に見つかる素数（範囲内の最大の素数）を後方から探索します。
4. 両者の差を計算して返します。

この方法により、素数判定を毎回行う必要がなくなり、各クエリを高速に処理できます。

実装例

#include <bits/stdc++.h>
using namespace std;

bool primeNumber[100005];

// エラトステネスの篩で素数表を作成
void findPrimes(){
    memset(primeNumber, true, sizeof(primeNumber));
    for (int i = 2; i * i < 100005; i++) {
        if (primeNumber[i]) {
            for (int j = i + i; j < 100005; j += i)
                primeNumber[j] = false;
        }
    }
}

// 範囲 [L, R] 内の素数の最大差を返す
int findPrimeInRange(int L, int R) {
    int LPrime = 0; // 最小の素数
    int RPrime = 0; // 最大の素数
    for(int i = L; i <= R; i++){
        if(primeNumber[i] == true){
            LPrime = i;
            break;
        }
    }
    for(int j = R; j >= L; j--){
        if(primeNumber[j] == true){
            RPrime = j;
            break;
        }
    }
    return (RPrime - LPrime);
}

int main() {
    int Q = 3;
    int query[Q][2] = {{4, 15}, {32, 37}, {54, 1100}};
    findPrimes();
    for (int i = 0; i < Q; i++)
        cout<<"For query "<<(i+1)<<": The maximum difference between primes numbers is "<<findPrimeInRange(query[i][0], query[i][1])<<"\n";
    return 0;
}

出力

For query 1: The maximum difference between primes numbers is 8
For query 2: The maximum difference between primes numbers is 0
For query 3: The maximum difference between primes numbers is 1038

計算量の目安

• 前処理（素数表の作成）： エラトステネスの篩により O(N log log N)（N は上限値）。
• 各クエリ： 最悪の場合 O(R − L)。範囲が広い場合でも、素数表参照のみで済むため高速です。

まとめ

範囲内の素数の最大差を求める問題では、エラトステネスの篩による事前計算が鍵となります。素数表を一度作成しておけば、複数のクエリに対しても素数判定を繰り返すことなく、最小の素数と最大の素数を簡単に特定でき、差を即座に算出できます。クエリが大量にあるような競技プログラミングの場面でも、この手法は非常に有効です。