C++で指定された長さの連続する合成数の範囲を求める方法

正整数 n が与えられたとき、「範囲内のすべての数が合成数であり、かつ範囲の長さがちょうど n となる」ような正整数の範囲を求める問題を考えます。条件を満たす範囲が複数存在する場合は、そのうちのどれか1つを出力すれば構いません。なお、合成数（composite number）とは「1 とその数自身以外に、少なくとも1つの約数を持つ数」のことです。

アルゴリズムの考え方

範囲の長さが n である以上、先頭の数を a とすると、範囲内の残りの数は a + 1, a + 2, …, a + n − 1 となり、これらがすべて合成数でなければなりません。

ここで役立つのが階乗（factorial）の性質です。正整数 p に対して、p! は 2, 3, 4, …, p − 1 のすべてを約数として持ちます。したがって、2 ≤ i ≤ p を満たす任意の i について、p! + i は必ず i を約数に含むため、必ず合成数になります。

つまり、p! + 2, p! + 3, …, p! + p − 1 はすべて合成数であり、範囲 [p! + 2, p! + p − 1] を出力すればよいことになります。この範囲に含まれる数は p − 2 個なので、長さ n の範囲を得るには p = n + 2 と置きます。こうして得られる範囲は [(n+2)! + 2, (n+2)! + n + 1] となり、ちょうど n 個の連続する合成数から構成されます。

C++での実装例

#include<iostream>
using namespace std;
int fact (int n) {
    if (n == 0)
        return 1;
    return n * fact(n-1);
}
void showRange(int n) {
    int a = fact(n + 2) + 2;
    int b = a + n - 1;
    cout << "[" << a << ", " << b << "]";
}
int main() {
    int n = 3;
    showRange(n);
}

コードの解説

fact 関数は再帰呼び出しによって階乗を計算します。showRange 関数では、範囲の先頭を a = (n + 2)! + 2 とし、末尾を b = a + n − 1 として求め、その範囲を標準出力に表示します。

出力結果

[122, 124]

例として n = 3 の場合、(n + 2)! = 5! = 120 となるため、範囲は [122, 124] になります。122 = 2 × 61、123 = 3 × 41、124 = 4 × 31 と、いずれも合成数であることが確認できます。

注意点

階乗は極めて大きな値に増加するため、n が大きくなると int 型ではすぐにオーバーフローを起こします。実用上は long long 型や多倍長整数ライブラリの利用を検討してください。