【C++】差がnとなる2つの合成数を見つける方法

整数 n が与えられたとき、その差がちょうど n になる2つの合成数（素数ではない数）a と b を求める問題を考えます。

例えば、入力が n = 512 の場合、出力は 5120 と 4608 となります。実際に確認すると、5120 − 4608 = 512 であり、両方とも合成数なので条件を満たしています。

解法のアプローチ

この問題は一見すると探索が必要そうに思えますが、実は非常にシンプルな数学的性質を利用すれば、即座に答えを導き出せます。

答えは、10 × n と 9 × n を出力するだけです。

なぜこの方法が有効なのか？

• 10 × n は必ず 10 を約数に持つため、常に合成数になります。
• 9 × n は必ず 9 を約数に持つため、常に合成数になります。
• 両者の差は (10 × n) − (9 × n) = n となり、問題の条件を満たします。

このように、任意の正の整数 n に対して、この方法は必ず正しい答えを返します。

C++での実装例

それでは、実際のコードを見てみましょう。

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

void solve(int n) {
    cout << 10 * n << ", " << 9 * n;
}

int main() {
    int n = 512;
    solve(n);
    return 0;
}

入力

512

出力

5120, 4608

まとめ

この問題は、「ある数の倍数は必ず合成数になる」という合成数の基本的な性質を利用することで、計算量 O(1) で解くことができます。複雑な探索アルゴリズムや素数判定は一切不要で、単純な掛け算だけで答えが得られる点がこの解法の魅力です。競技プログラミングにおいても、このような数学的なひらめきが求められる典型例と言えるでしょう。