Check for an array element that is co | Python3 implementation of the approach ; Stores smallest prime factor for every number ; Hash to store prime factors count ; Function to calculate SPF ( SmallestPrime Factor ) for every number till MAXN ; Separately marking spf for every even number as 2 ; Checking if i is prime ; Marking SPF for all numbers divisible by i ; Marking spf [ j ] if it is not previously marked ; Function to store the prime factors after dividing by the smallest prime factor at every step ; Storing the count of prime factors in hash ; Function that returns true if there are no common prime factors between x and other numbers of the array ; Checking whether it common prime factor with other numbers ; Function that returns true if there is an element in the array which is coprime with all the other elements of the array ; Using sieve for generating prime factors ; Checking the common prime factors with other numbers ; Driver code
MAXN = 1000001 NEW_LINE spf = [ i for i in range ( MAXN ) ] NEW_LINE hash1 = [ 0 for i in range ( MAXN ) ] NEW_LINE def sieve ( ) : NEW_LINE INDENT for i in range ( 4 , MAXN , 2 ) : NEW_LINE INDENT spf [ i ] = 2 NEW_LINE DEDENT for i in range ( 3 , MAXN ) : NEW_LINE INDENT if i * i >= MAXN : NEW_LINE INDENT break NEW_LINE DEDENT if ( spf [ i ] == i ) : NEW_LINE INDENT for j in range ( i * i , MAXN , i ) : NEW_LINE INDENT if ( spf [ j ] == j ) : NEW_LINE INDENT spf [ j ] = i NEW_LINE DEDENT DEDENT DEDENT DEDENT DEDENT def getFactorization ( x ) : NEW_LINE INDENT while ( x != 1 ) : NEW_LINE INDENT temp = spf [ x ] NEW_LINE if ( x % temp == 0 ) : NEW_LINE INDENT hash1 [ spf [ x ] ] += 1 NEW_LINE x = x // spf [ x ] NEW_LINE DEDENT while ( x % temp == 0 ) : NEW_LINE INDENT x = x // temp NEW_LINE DEDENT DEDENT DEDENT def check ( x ) : NEW_LINE INDENT while ( x != 1 ) : NEW_LINE INDENT temp = spf [ x ] NEW_LINE if ( x % temp == 0 and hash1 [ temp ] > 1 ) : NEW_LINE INDENT return False NEW_LINE DEDENT while ( x % temp == 0 ) : NEW_LINE INDENT x = x // temp NEW_LINE DEDENT DEDENT return True NEW_LINE DEDENT def hasValidNum ( arr , n ) : NEW_LINE INDENT sieve ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT getFactorization ( arr [ i ] ) NEW_LINE DEDENT for i in range ( n ) : NEW_LINE INDENT if ( check ( arr [ i ] ) ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT return False NEW_LINE DEDENT arr = [ 2 , 8 , 4 , 10 , 6 , 7 ] NEW_LINE n = len ( arr ) NEW_LINE if ( hasValidNum ( arr , n ) ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT