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ụ của chúng ta là in tất cả các số nguyên tố và số Fibonacci nhỏ hơn hoặc bằng n.

Hãy lấy một ví dụ để hiểu 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ố này, số nguyên tố là 2 3 5 13.

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

Đối với điều này, chúng tôi sẽ tìm thấy tất cả các số nguyên tố nhỏ hơn hoặc bằng n. Và kiểm tra xem các số được tạo có nằm trong chuỗi Fibonacci hay không.

Nếu một số nằm trong chuỗi Fibonacci , thì nó ở dạng 5i2 + 4 hoặc 5i2 - 4.

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

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<<"All prime Fibonacci numbers less than "<<N<<" are :\n";
   printPrimeAndFibnacciNumbers(N);
   return 0;
}

Đầu ra

All prime Fibonacci numbers less than 50 are :
23513