Check if GCD of all Composite Numbers in an array divisible by K is a Fibonacci Number or not | Java Program for the above approach ; Function to check if a number is composite or not ; Corner cases ; Check if the number is divisible by 2 or 3 or not ; Check if n is a multiple of any other prime number ; Function to check if a number is a Perfect Square or not ; Function to check if a number is a Fibonacci number or not ; If 5 * n ^ 2 + 4 or 5 * n ^ 2 - 4 or both are perfect square ; Function to check if GCD of composite numbers from the array a [ ] which are divisible by k is a Fibonacci number or not ; Traverse the array ; If array element is composite and divisible by k ; Calculate GCD of all elements in compositeset ; If GCD is Fibonacci ; Recursive function to return gcd of a and b ; Driver Code
import java . util . * ; class GFG { static boolean isComposite ( int n ) { if ( n <= 1 ) return false ; if ( n <= 3 ) return false ; if ( n % 2 == 0 n % 3 == 0 ) return true ; for ( int i = 5 ; i * i <= n ; i = i + 6 ) if ( n % i == 0 || n % ( i + 2 ) == 0 ) return true ; return false ; } static boolean isPerfectSquare ( int x ) { int s = ( int ) Math . sqrt ( x ) ; return ( s * s == x ) ; } static boolean isFibonacci ( int n ) { return isPerfectSquare ( 5 * n * n + 4 ) || isPerfectSquare ( 5 * n * n - 4 ) ; } static void ifgcdFibonacci ( int a [ ] , int n , int k ) { Vector < Integer > compositeset = new Vector < > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( isComposite ( a [ i ] ) && a [ i ] % k == 0 ) { compositeset . add ( a [ i ] ) ; } } int gcd = compositeset . get ( 0 ) ; for ( int i = 1 ; i < compositeset . size ( ) ; i ++ ) { gcd = __gcd ( gcd , compositeset . get ( i ) ) ; if ( gcd == 1 ) { break ; } } if ( isFibonacci ( gcd ) ) { System . out . print ( " Yes " ) ; return ; } System . out . print ( " No " ) ; return ; } static int __gcd ( int a , int b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 34 , 2 , 4 , 8 , 5 , 7 , 11 } ; int n = arr . length ; int k = 2 ; ifgcdFibonacci ( arr , n , k ) ; } }