与えられた仮説を反証する数を見つけるためのC++コード

正の整数 n が与えられたとします。ここで、「ある正の整数 n が存在し、任意の正の整数 m に対して (n・m + 1) が常に素数となる」という仮説を考えます。この仮説が誤りであることを証明するには、反例となる m を見つける必要があります。

例えば、入力が n = 12 の場合、出力は 10 になります。これは 12 × 10 + 1 = 121 が素数ではないためです(121 = 11 × 11 と素因数分解できるからです)。

解法のアプローチ

この問題は、以下のシンプルな手順で解くことができます。

• n が 3 未満の場合:n + 2 を返す
• それ以外の場合:n - 2 を返す

if n < 3, then:
    return n + 2
Otherwise
    return n - 2

なぜこれで反例になるのか?

この方法が機能する理由は数学的にきれいに説明できます。n ≥ 3 のときに m = n - 2 を選ぶと、次のようになります。

n・(n - 2) + 1 = n² - 2n + 1 = (n - 1)²

つまり結果は完全平方数となり、n - 1 ≥ 2 であるため必ず合成数になります。同様に、n < 3 の場合に m = n + 2 を選ぶと、n・(n + 2) + 1 = (n + 1)² となり、やはり素数ではありません。したがって、どのような n に対しても反例が必ず存在することになります。

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
int solve(int n){
    if (n < 3)
        return n + 2;
    else
        return n - 2;
}
int main(){
    int n = 12;
    cout << solve(n) << endl;
}

入力

12

出力

10

このように、複雑な素数判定を行わなくても、代数的な性質を利用すれば O(1) の計算量で反例を求められます。