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: using System ; using System . Collections . Generic ; class GFG { static bool [ ] isPrime ; static HashSet < int > createhashmap ( int Max ) { HashSet < int > hashmap = new HashSet < int > ( ) ; int curr = 1 ; int prev = 0 ; hashmap . Add ( prev ) ; while ( curr < Max ) { hashmap . Add ( curr ) ; int temp = curr ; curr = curr + prev ; prev = temp ; } return hashmap ; } static void SieveOfEratosthenes ( int Max ) { isPrime = new bool [ Max ] ; for ( int i = 0 ; i < Max ; i ++ ) isPrime [ i ] = 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 ; } } } } static void cntFibonacciPrime ( int [ ] arr , int N ) { int Max = arr [ 0 ] ; for ( int i = 1 ; i < N ; i ++ ) { Max = Math . Max ( Max , arr [ i ] ) ; } SieveOfEratosthenes ( Max ) ; HashSet < int > hashmap = createhashmap ( Max ) ; for ( int i = 0 ; i < N ; i ++ ) { if ( arr [ i ] == 1 ) continue ; if ( ( hashmap . Contains ( arr [ i ] ) ) && ! isPrime [ arr [ i ] ] ) { Console . Write ( arr [ i ] + " ▁ " ) ; } } } public static void Main ( String [ ] args ) { int [ ] arr = { 13 , 55 , 7 , 3 , 5 , 21 , 233 , 144 , 89 } ; int N = arr . Length ; cntFibonacciPrime ( arr , N ) ; } }