C++でN以下の乗法的素数をすべて出力する方法

この記事では、整数 n が与えられたときに、n 以下のすべての乗法的素数(マルチプリカティブ素数)を見つけて出力する方法を、C++のコード例とともにわかりやすく解説します。

乗法的素数とは?

乗法的素数とは、「各桁の数字の積もまた素数になる」という性質を持つ素数のことです。たとえば、2、3、5、7、13、17 などが該当します。

一方で、23 は素数ではありますが、各桁の積が 2 × 3 = 6 となり素数ではないため、乗法的素数には分類されません。

問題例

入力: n = 9
出力: 2 3 5 7

解き方のアプローチ

この問題は、次の手順で効率的に解くことができます。

1. 素数の列挙: エラトステネスの篩(ふるい)を用いて、n 以下のすべての素数を求めます。
2. 桁の積の計算: 各素数について、その数字を構成する各桁の積を計算します。
3. 判定と出力: 桁の積も素数であれば、その数は乗法的素数であるため出力します。

C++での実装例

以下のプログラムは、上記のアルゴリズムを実装したものです。

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

// 各桁の数字の積を計算する関数
int digitMultiply(int n) {
    int prod = 1;
    while (n) {
        prod = prod * (n % 10);
        n = n / 10;
    }
    return prod;
}

// n 以下の乗法的素数をすべて出力する関数
void generateMprime(int n) {
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;

    // エラトステネスの篩で素数表を作成
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }

    // 素数であり、かつ桁の積も素数である数を出力
    for (int i = 2; i <= n; i++) {
        if (prime[i] && prime[digitMultiply(i)])
            cout << i << "\t";
    }
}

int main() {
    int n = 10;
    cout << "All multiplicative Prime Numbers =< " << n << " are :\n";
    generateMprime(n);
}

実行結果

All multiplicative Prime Numbers =< 10 are −
2 3 5 7

計算量と補足

エラトステネスの篩による素数生成の時間計算量は O(n log log n) であり、各数値の桁の積の計算は桁数に依存して O(log n) 程度で済みます。そのため、この手法は非常に効率的です。

なお、サンプルコード中の bool prime[n + 1] は可変長配列(VLA)を使用しており、これはGCCなどの拡張機能です。移植性を高めたい場合は、std::vector<bool> を使うことをおすすめします。