Prime Numbers and Fibonacci in C++

In this problem, we are given a number n. Our task is to print all prime and Fibonacci numbers less than or equal to n.

Let’s take an example to understand the problem

Input: n = 30
Output: 2 3 5 13

Explanation

Fibonacci numbers less than 30 are : 1 1 2 3 5 8 13 21.

Out of these numbers, prime numbers are 2 3 5 13.

To solve this problem, we have to check if all numbers of the Fibonacci series less than n is a prime number.

For this, we will find all prime numbers less than or equal to n. And check if the generated numbers are contained in the Fibonacci series or not.

If a number is in the Fibonacci series, then it is in form 5i2 + 4 or 5i2 - 4.

Program to show the implementation of our solution,

Example

 Live Demo

#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;
}

Output

All prime Fibonacci numbers less than 50 are :
23513