C++でn以下の「素数かつフィボナッチ数」をすべて出力する方法

この問題では、ある数値 n が与えられ、n 以下の数の中で素数であり、かつフィボナッチ数でもあるものをすべて出力することが求められます。

問題の例

入力: n = 30
出力: 2 3 5 13

解説

30 未満のフィボナッチ数は「1, 1, 2, 3, 5, 8, 13, 21」です。この中で素数であるのは「2, 3, 5, 13」の4つとなります。

解き方のアプローチ

この問題を解くには、n 以下のフィボナッチ数をすべて求め、それぞれが素数かどうかを判定する方法が考えられます。しかし、より効率的なのは逆のアプローチです。

1. エラトステネスの篩（ふるい）を使って、n 以下のすべての素数を求める。
2. 各素数がフィボナッチ数列に含まれるかどうかを判定する。

ここで重要なのが、ある数 x がフィボナッチ数であるかどうかは、「5x² + 4」または「5x² − 4」が完全平方数になるかどうかで判定できるという数学的な性質です。これを使えば、フィボナッチ数列を実際に生成しなくても高速に判定できます。

C++による実装例

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

// 完全平方数かどうかを判定する関数
bool isSquare(int n) {
    int sr = sqrt(n);
    return (sr * sr == n);
}

// 素数かつフィボナッチ数を出力する関数
void printPrimeAndFibonacciNumbers(int n) {
    bool primeNumbers[n + 1];
    memset(primeNumbers, true, sizeof(primeNumbers));

    // エラトステネスの篩で素数を求める
    for (int p = 2; p * p <= n; p++) {
        if (primeNumbers[p] == true) {
            for (int i = p * 2; i <= n; i += p)
                primeNumbers[i] = false;
        }
    }

    // 素数の中からフィボナッチ数の条件を満たすものを出力
    for (int i = 2; i <= n; i++)
        if (primeNumbers[i] && (isSquare(5*i*i+4) || isSquare(5*i*i-4)))
            cout << i << "\t";
}

int main() {
    int N = 50;
    cout << "50以下の素数かつフィボナッチ数は:\n";
    printPrimeAndFibonacciNumbers(N);
    return 0;
}

実行結果

50以下の素数かつフィボナッチ数は:
2	3	5	13

処理のポイント

• isSquare 関数: 平方根を求め、その2乗が元の値と一致するかで完全平方数を判定します。
• エラトステネスの篩: 2から順に素数で割り切れる数を除外していく、定番の素数生成アルゴリズムです。計算量は O(n log log n) と非常に効率的です。
• フィボナッチ判定: 「5i² + 4」または「5i² − 4」が完全平方数であれば、その数はフィボナッチ数であると判定できます。

このように、数学的な性質と効率的なアルゴリズムを組み合わせることで、n 以下の素数かつフィボナッチ数を簡単に求めることができます。