C++でNまでの交互素数（1つおきの素数）を出力する方法

本記事では、C++を使ってNまでの交互素数（1つおきの素数）をすべて出力する方法を解説します。交互素数とは、Nまでの素数を小さい順に並べたとき、1つ飛ばしで選んだ素数のことです。

例えば N = 15 の場合を考えてみましょう。15までの素数は {2, 3, 5, 7, 11, 13} であり、これらから1つおきに選ぶと、交互素数は {2, 5, 11} となります。それでは、この問題をどのように解けばよいのか見ていきましょう。

アルゴリズムの考え方

まずエラトステネスの篩を用いてNまでの素数をすべて求めます。その後、ブール型のフラグ変数を使って素数を走査し、フラグが立っているときだけ出力することで、1つおきの素数を取り出します。

printAlternatePrime(N) の手順

Begin
    サイズ N + 1 のブール配列 prime を定義し、すべて true(1) で初期化する
    for p := 2, p^2 <= N の間、p を 1 ずつ増やしながら繰り返す
        if prime[p] が true ならば
            p のすべての倍数に対応する prime 配列の要素を false(0) にする
        end if
    done
    フラグをセットする
    for p := 2 to n まで繰り返す
        if prime[p] が true ならば
            if フラグが立っているならば
                p を出力し、フラグをリセットする
            else
                フラグをセットする
            end if
        end if
    done
End

C++による実装例

#include<iostream>
using namespace std;
void printAlternatePrime(int n) {
    bool prime[n + 1];
    for(int i = 0; i<=n; i++) {
        prime[i] = true; // すべての要素を true で初期化
    }
    // エラトステネスの篩で合成数を除外
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * 2; i <= n; i += p) // p の倍数をすべて false にする
                prime[i] = false;
        }
    }
    bool prime_flag = true;
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            if (prime_flag) {
                cout << p << " ";   // 素数を出力
                prime_flag = false;
            } else {
                prime_flag = true;  // 次の素数を出力できるようにフラグを立てる
            }
        }
    }
}
main() {
    int n;
    cout << "上限値を入力してください: ";
    cin >> n;
    cout << "交互素数は次の通りです: ";
    printAlternatePrime(n);
}

実行結果

上限値を入力してください: 20
交互素数は次の通りです: 2 5 11 17

処理のポイント

このプログラムのポイントは以下の2点です。

1. エラトステネスの篩による高速な素数判定： 各素数 p について、その倍数を順番に false にしていくことで、O(N log log N) の計算量で効率よく素数表を作成できます。

2. フラグ変数による間引き処理： 素数を見つけるたびにフラグを反転させることで、「出力する」「スキップする」を交互に切り替え、1つおきの素数だけを出力しています。