Check if GCD of all Composite Numbers in an array divisible by K is a Fibonacci Number or not | Python3 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 ; Driver Code
import math NEW_LINE def isComposite ( n ) : NEW_LINE INDENT if n <= 1 : NEW_LINE INDENT return False NEW_LINE DEDENT if n <= 3 : NEW_LINE INDENT return False NEW_LINE DEDENT if n % 2 == 0 or n % 3 == 0 : NEW_LINE INDENT return True NEW_LINE DEDENT i = 5 NEW_LINE while i * i <= n : NEW_LINE INDENT if ( ( n % i == 0 ) or ( n % ( i + 2 ) == 0 ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT i += 6 NEW_LINE DEDENT return False NEW_LINE DEDENT def isPerfectSquare ( x ) : NEW_LINE INDENT s = int ( math . sqrt ( x ) ) NEW_LINE return ( s * s == x ) NEW_LINE DEDENT def isFibonacci ( n ) : NEW_LINE INDENT return ( isPerfectSquare ( 5 * n * n + 4 ) or isPerfectSquare ( 5 * n * n - 4 ) ) NEW_LINE DEDENT def ifgcdFibonacci ( a , n , k ) : NEW_LINE INDENT compositeset = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( isComposite ( a [ i ] ) and a [ i ] % k == 0 ) : NEW_LINE INDENT compositeset . append ( a [ i ] ) NEW_LINE DEDENT DEDENT gcd = compositeset [ 0 ] NEW_LINE for i in range ( 1 , len ( compositeset ) , 1 ) : NEW_LINE INDENT gcd = math . gcd ( gcd , compositeset [ i ] ) NEW_LINE if gcd == 1 : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT if ( isFibonacci ( gcd ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE return NEW_LINE DEDENT print ( " No " ) NEW_LINE return NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 34 , 2 , 4 , 8 , 5 , 7 , 11 ] NEW_LINE n = len ( arr ) NEW_LINE k = 2 NEW_LINE ifgcdFibonacci ( arr , n , k ) NEW_LINE DEDENT