C++で解説：隣接する2数は互いに素でなく、連続する3数は互いに素となる数列を出力するプログラム

はじめに

このチュートリアルでは、「隣接する2つの数が互いに素ではなく、かつ連続する3つの数が互いに素となる」ような数列を出力するC++プログラムについて解説します。

問題の概要

整数Nが与えられたとき、10⁹未満のN個の整数を出力する必要があります。出力する数列は、以下の2つの条件を満たさなければなりません。

• 条件1: 隣接する2つの数は互いに素でない（最大公約数が1より大きい）
• 条件2: 連続する3つの整数の組は互いに素である（最大公約数が1）

例えば、N=4が与えられた場合、両方の条件を満たす数列は次のようになります。

6 15 35 14

この出力を検証してみましょう。

• gcd(6, 15) = 3、gcd(15, 35) = 5、gcd(35, 14) = 7 → どの隣接ペアも互いに素ではありません
• gcd(6, 15, 35) = 1、gcd(15, 35, 14) = 1 → どの3連続組も互いに素です

アルゴリズムのアプローチ

この問題を解く鍵となるアイデアは、「連続する素数の積」を利用することです。素数を p₁, p₂, p₃, … とすると、p₁×p₂, p₂×p₃, p₃×p₄, … という数列を構成します。

• 隣接する2つの数は共通の素因数を1つ持つため、互いに素にはなりません
• 連続する3つの数に共通する素因数は存在しないため、互いに素になります

C++での実装例

#include <bits/stdc++.h>
using namespace std;
#define limit 1000000000
#define MAX_PRIME 2000000
#define MAX 1000000
#define I_MAX 50000
map<int, int> map1;
int b[MAX];
int p[MAX];
int j = 0;
bool prime[MAX_PRIME + 1];
void sieve(int n){
    memset(prime, true, sizeof(prime));
    for (int p = 2; p * p <= n; p++){
       if (prime[p] == true){
          for (int i = p * p; i <= n; i += p)
             prime[i] = false;
       }
    }
    for (int p = 2; p <= n; p++){
       if (prime[p]) {
          b[j++] = p;
       }
    }
}
int gcdiv(int a, int b){
    if (b == 0)
       return a;
    return gcdiv(b, a % b);
}
// 条件を満たす数列を出力する関数
void print_elements(int n){
    sieve(MAX_PRIME);
    int i, g, k, l, m, d;
    int ar[I_MAX + 2];
    for (i = 0; i < j; i++){
       if ((b[i] * b[i + 1]) > limit)
          break;
       p[i] = b[i];
       map1[b[i] * b[i + 1]] = 1;
    }
    d = 550;
    bool flag = false;
    for (k = 2; (k < d - 1) && !flag; k++){
       for (m = 2; (m < d) && !flag; m++){
          for (l = m + k; l < d; l += k){
             if (((b[l] * b[l + k]) < limit)
                && (l + k) < d && p[i - 1] != b[l + k]
                && p[i - 1] != b[l] && map1[b[l] * b[l + k]] != 1){
                if (map1[p[i - 1] * b[l]] != 1){
                   p[i] = b[l];
                   map1[p[i - 1] * b[l]] = 1;
                   i++;
                }
            }
            if (i >= I_MAX) {
               flag = true;
               break;
            }
         }
      }
   }
    for (i = 0; i < n; i++)
       ar[i] = p[i] * p[i + 1];
    for (i = 0; i < n - 1; i++)
       cout << ar[i] << " ";
    g = gcdiv(ar[n - 1], ar[n - 2]);
    cout << g * 2 << endl;
}
int main(){
    int n = 4;
    print_elements(n);
    return 0;
}

出力結果

6 15 35 14

コードの解説

1. sieve関数： エラトステネスの篩を用いて、2からMAX_PRIME（2,000,000）までのすべての素数を配列bに格納します。
2. gcdiv関数： ユークリッドの互除法を再帰的に用いて、2つの整数の最大公約数を求めます。
3. print_elements関数： まず、積が10⁹を超えない範囲で連続する素数のペアをmap1に登録します。その後、重複する積を避けながら素数の選択を拡張し、「連続する素数の積」からなる数列arを構築します。
4. 最後の要素の調整： 最後の要素は、直前の2つの要素の最大公約数gの2倍（g×2）として出力します。これにより、隣接する数との共通因数を保ちつつ、3連続の互いに素という条件も満たすことができます。

まとめ

このように、連続する素数の積を組み合わせることで、「隣接する2数は互いに素でないが、連続する3数は互いに素である」という一見複雑な条件を満たす数列を効率的に生成できます。エラトステネスの篩による素数生成と、ユークリッドの互除法による最大公約数の計算は、競技プログラミングでも頻出のテクニックなので、ぜひマスターしておきましょう。