C++で数値が素数に挟まれているかどうかを判定する方法

素数に挟まれた数とは？

「素数に挟まれた数」とは、ある数値の直前の数と直後の数が、どちらも素数であるような数のことを指します。

例えば 642 の場合を見てみましょう。642の直前の数は 641、直後の数は 643 であり、この2つはどちらも素数です。したがって、642は素数に挟まれている数だと言えます。

判定方法は非常にシンプルです。対象となる数を n としたとき、n-1 と n+1 の両方が素数かどうかを確認するだけで済みます。

アルゴリズムの流れ

1. 判定したい数値 n を入力として受け取る
2. n-1 が素数かどうかを判定する
3. n+1 が素数かどうかを判定する
4. 両方が素数であれば true、そうでなければ false を返す

C++での実装例

#include <iostream>
#include <set>
#define N 100005
using namespace std;

// 素数判定関数
bool isPrime(int n) {
    if (n == 0 || n == 1)
        return false;
    for (int i = 2; i <= n / 2; i++)
        if (n % i == 0)
            return false;
    return true;
}

// 素数に挟まれているかを判定する関数
bool isSandwichedPrime(int n) {
    if (isPrime(n - 1) && isPrime(n + 1))
        return true;
    return false;
}

int main() {
    int n = 642;
    if (isSandwichedPrime(n)) {
        cout << n << " is Sandwiched between primes: " << n - 1 << " and " << n + 1;
    } else {
        cout << n << " is not Sandwiched between primes";
    }
}

コードの解説

• isPrime関数：引数が0または1の場合は素数ではないため false を返します。その後、2から n/2 までの整数で順番に割り切れるかを確認し、割り切れる数がひとつでもあれば素数ではないと判断します。
• isSandwichedPrime関数：n-1 と n+1 のそれぞれに対して isPrime を呼び出し、両方が素数であれば true を返します。
• main関数：判定したい数値（ここでは642）を渡し、結果に応じてメッセージを出力します。

実行結果

642 is Sandwiched between primes: 641 and 643

まとめ

このように、ある数が素数に挟まれているかどうかは、前後の数が素数であるかをチェックするだけで簡単に判定できます。ただし、上記の isPrime 関数は2から n/2 まで順番に調べるため、計算量は O(n) となります。より大きな数値を扱う場合は、試し割りの範囲を √n まで縮める、あるいはエラトステネスの篩を活用することで、処理を大幅に高速化できます。