text: Count composite fibonacci numbers from given array | C ++ program to implement the above approach ; Function to find all Fibonacci numbers up to Max ; Store all Fibonacci numbers upto Max ; Stores previous element of Fibonacci sequence ; Stores previous element of Fibonacci sequence ; Insert prev into hashmap ; Insert all the Fibonacci numbers up to Max ; Insert curr into hashmap ; Stores curr into temp ; Update curr ; Update prev ; Function to find all Composite numbers up to Max ; isPrime [ i ] : Stores if i is a prime number or not ; Calculate all prime numbers up to Max using Sieve of Eratosthenes ; If P is a prime number ; Set all multiple of P as non - prime ; Update isPrime ; Function to find the numbers which is both a composite and Fibonacci number ; Stores the largest element of the array ; Traverse the array arr [ ] ; Update Max ; isPrim [ i ] check i is a prime number or not ; Stores all the Fibonacci numbers ; Traverse the array arr [ ] ; current element is not a composite number ; If current element is a Fibonacci and composite number ; Print current element ; Driver Code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; set < int > createhashmap ( int Max ) { set < int > hashmap ; int curr = 1 ; int prev = 0 ; hashmap . insert ( prev ) ; while ( curr <= Max ) { hashmap . insert ( curr ) ; int temp = curr ; curr = curr + prev ; prev = temp ; } return hashmap ; } vector < bool > SieveOfEratosthenes ( int Max ) { vector < bool > isPrime ( Max , true ) ; isPrime [ 0 ] = false ; isPrime [ 1 ] = false ; for ( int p = 2 ; p * p <= Max ; p ++ ) { if ( isPrime [ p ] ) { for ( int i = p * p ; i <= Max ; i += p ) { isPrime [ i ] = false ; } } } return isPrime ; } int cntFibonacciPrime ( int arr [ ] , int N ) { int Max = arr [ 0 ] ; for ( int i = 1 ; i < N ; i ++ ) { Max = max ( Max , arr [ i ] ) ; } vector < bool > isPrime = SieveOfEratosthenes ( Max ) ; set < int > hashmap = createhashmap ( Max ) ; for ( int i = 0 ; i < N ; i ++ ) { if ( arr [ i ] == 1 ) continue ; if ( ( hashmap . count ( arr [ i ] ) ) && ! isPrime [ arr [ i ] ] ) { cout << arr [ i ] << " ▁ " ; } } } int main ( ) { int arr [ ] = { 13 , 55 , 7 , 3 , 5 , 21 , 233 , 144 , 89 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cntFibonacciPrime ( arr , N ) ; return 0 ; }