C++で隣接要素が互いに割り切れない昇順配列を生成する方法

整数 n が与えられたとします。ここで、n 個の要素からなる配列 A を作成することを考えます。配列 A は次の条件を満たす必要があります。

• A は昇順にソートされている
• すべての要素は互いに異なる（重複がない）
• インデックスを 1 から始めた場合、2 ≤ i ≤ n を満たすすべての i について、A[i] が A[i-1] で割り切れない

例えば、入力が n = 7 の場合、出力は [2, 3, 4, 5, 6, 7, 8] となります。

解法のアプローチ

この問題は実は非常にシンプルです。2 から n+1 までの連続する整数をそのまま並べるだけで条件を満たす配列が得られます。連続する整数において、大きい方の数を小さい方の数で割ると必ず余りが発生するため、隣接要素どうしが割り切れることはありません。したがって、この方法で常に正解となります。

アルゴリズムの手順

1. 変数 i を 2 で初期化します。
2. i が n + 1 以下である間、i を出力し、i を 1 ずつ増やしていきます。

C++による実装例

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

#include <bits/stdc++.h>
using namespace std;
void solve(int n){
    for (int i = 2; i <= n + 1; i++){
        printf("%d, ", i);
    }
}
int main(){
    int n = 7;
    solve(n);
}

入力

7

出力

2, 3, 4, 5, 6, 7, 8

計算量について

このアルゴリズムは配列を一度だけ走査して出力するため、時間計算量は O(n)、追加のメモリ使用量は O(1) となり、非常に効率的です。