Số nguyên tố và Fibonacci trong C++

Trong bài toán này, chúng ta được cho một số n. Nhiệm vụ là in ra tất cả các số vừa là số nguyên tố vừa là số Fibonacci nhỏ hơn hoặc bằng n.

Hãy xem ví dụ sau để hiểu rõ vấn đề:

Input: n = 30 Output: 2 3 5 13

Giải thích

Các số Fibonacci nhỏ hơn 30 là: 1 1 2 3 5 8 13 21.

Trong đó, các số nguyên tố là 2 3 5 13.

Để giải quyết, ta kiểm tra xem các số trong dãy Fibonacci nhỏ hơn n có phải là số nguyên tố hay không.

Ta tìm tất cả các số nguyên tố <= n. Sau đó kiểm tra xem các số đó có nằm trong dãy Fibonacci hay không.

Nếu một số nằm trong dãy Fibonacci, nó có dạng 5i² + 4 hoặc 5i² - 4.

Chương trình minh họa triển khai giải pháp:

Ví dụ

#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<<"Tất cả các số Fibonacci nguyên tố nhỏ hơn "<<N<<" là :\n";    printPrimeAndFibnacciNumbers(N);    return 0; }

Kết quả

Tất cả các số Fibonacci nguyên tố nhỏ hơn 50 là : 2 3 5 13