【C++】nより小さい最も近い素数を求めるアルゴリズムと実装方法

数値 n が与えられたとき、n より小さい最も近い素数を求める問題について解説します。

この問題は、n - 1 から順に素数かどうかをチェックしていけば、簡単に答えを見つけることができます。まずは具体例を見てみましょう。

入力例と出力例

入力:

10

出力:

7

10 未満の数の中で最も近い素数は 7 であるため、出力は 7 となります。

アルゴリズム

解法の手順は以下の通りです。

• 数値 n を初期化します。
• n - 1 から 1 まで逆順にループを回します。
  • 最初に見つかった素数を返します。
• n 未満に素数が存在しない場合は -1 を返します。

C++での実装

上記のアルゴリズムを C++ で実装したコードが以下です。

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

bool isPrime(int n) {
    if (n == 2) {
        return true;
    }
    for (int i = 2; i <= ceil(sqrt(n)); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int getNearestPrimeNumber(int n) {
    for (int i = n - 1; i > 1; i--) {
        if (isPrime(i)) {
            return i;
        }
    }
    return -1;
}

int main() {
    int n = 20;
    cout << getNearestPrimeNumber(n) << endl;
    return 0;
}

コードのポイント

• isPrime 関数: 素数判定を行う関数です。2 の平方根までの整数で割り切れるかどうかを確認することで、効率的に判定できます。
• getNearestPrimeNumber 関数: n - 1 から降順に調べ、最初に見つかった素数を返します。

実行結果

上記のコードを実行すると、以下の結果が出力されます。

19

20 未満で最も近い素数は 19 なので、正しく出力されていることがわかります。

まとめ

n より小さい最も近い素数を求めるには、n - 1 から順に素数判定を行っていくのがシンプルで効果的な方法です。素数判定では平方根まで確認すれば十分なため、計算量を抑えることができます。