จำนวนเฉพาะและฟีโบนัชชี (Prime Fibonacci) ใน C++

ภาพรวมปัญหา

ได้รับตัวเลข n ต้องพิมพ์จำนวนที่เป็นทั้งจำนวนเฉพาะและเลขฟีโบนัชชี ที่น้อยกว่าหรือเท่ากับ n

ตัวอย่าง

Input: n = 30
Output: 2 3 5 13
Explanation: ฟีโบนัชชี ≤ 30: 1,1,2,3,5,8,13,21 → จำนวนเฉพาะ: 2,3,5,13

หลักการตรวจสอบเลขฟีโบนัชชี

จำนวน x เป็นเลขฟีโบนัชชี ก็ต่อเมื่อ 5x² + 4 หรือ 5x² - 4 เป็นจำนวนกำลังสองสมบูรณ์

วิธีแก้ปัญหา

1. หาจำนวนเฉพาะทั้งหมด ≤ n ด้วย Sieve of Eratosthenes
2. ตรวจสอบแต่ละจำนวนเฉพาะว่าเป็นเลขฟีโบนัชชีหรือไม่

ตัวอย่างโค้ด C++

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

bool isSquare(int n) {
    int sr = sqrt(n);
    return (sr * sr == n);
}

void printPrimeAndFibnacciNumbers(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) > 0 || isSquare(5*i*i - 4) > 0))
            cout << i << "\t";
}

int main() {
    int N = 50;
    cout << "All prime Fibonacci numbers less than " << N << " are :\n";
    printPrimeAndFibnacciNumbers(N);
    return 0;
}

ผลลัพธ์

All prime Fibonacci numbers less than 50 are : 2 3 5 13