Smallest number which is not coprime with any element of an array | Python 3 program for the above approach ; Function check if a number is prime or not ; Corner cases ; Check if n is divisible by 2 or 3 ; Check for every 6 th number . The above checking allows to skip middle 5 numbers ; Function to store primes in an array ; Function to find the smallest number which is not coprime with any element of the array arr [ ] ; Store the prime numbers ; Function call to fill the prime numbers ; Stores the answer ; Generate all non - empty subsets of the primes [ ] array ; Stores product of the primes ; Checks if temp is coprime with the array or not ; Check if the product temp is not coprime with the whole array ; If the product is not co - prime with the array ; Print the answer ; Driver Code ; Given array ; Stores the size of the array
MAX = 50 NEW_LINE import sys NEW_LINE from math import sqrt , gcd NEW_LINE def isPrime ( n ) : NEW_LINE INDENT if ( n <= 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT if ( n <= 3 ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( n % 2 == 0 or n % 3 == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT for i in range ( 5 , int ( sqrt ( n ) ) + 1 , 6 ) : NEW_LINE INDENT if ( n % i == 0 or n % ( i + 2 ) == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def findPrime ( primes ) : NEW_LINE INDENT global MAX NEW_LINE for i in range ( 2 , MAX + 1 , 1 ) : NEW_LINE INDENT if ( isPrime ( i ) ) : NEW_LINE INDENT primes . append ( i ) NEW_LINE DEDENT DEDENT DEDENT def findMinimumNumber ( arr , N ) : NEW_LINE INDENT primes = [ ] NEW_LINE findPrime ( primes ) NEW_LINE ans = sys . maxsize NEW_LINE n = len ( primes ) NEW_LINE for i in range ( 1 , ( 1 << n ) , 1 ) : NEW_LINE INDENT temp = 1 NEW_LINE for j in range ( n ) : NEW_LINE INDENT if ( i & ( 1 << j ) ) : NEW_LINE INDENT temp *= primes [ j ] NEW_LINE DEDENT DEDENT check = True NEW_LINE for k in range ( N ) : NEW_LINE INDENT if ( gcd ( temp , arr [ k ] ) == 1 ) : NEW_LINE INDENT check = False NEW_LINE break NEW_LINE DEDENT DEDENT if ( check ) : NEW_LINE INDENT ans = min ( ans , temp ) NEW_LINE DEDENT DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 3 , 4 , 6 , 7 , 8 , 9 , 10 ] NEW_LINE N = len ( arr ) NEW_LINE findMinimumNumber ( arr , N ) NEW_LINE DEDENT