Check for an array element that is co | PHP implementation of the approach ; Stores smallest prime factor for every number ; Hash to store prime factors count ; Function to calculate SPF ( Smallest Prime Factor ) for every number till MAXN ; Marking smallest prime factor for every number to be itself ; 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
< ? php $ MAXN = 10001 ; $ spf = array_fill ( 0 , $ MAXN , 0 ) ; $ hash1 = array_fill ( 0 , $ MAXN , 0 ) ; function sieve ( ) { global $ spf , $ MAXN , $ hash1 ; $ spf [ 1 ] = 1 ; for ( $ i = 2 ; $ i < $ MAXN ; $ i ++ ) $ spf [ $ i ] = $ i ; for ( $ i = 4 ; $ i < $ MAXN ; $ i += 2 ) $ spf [ $ i ] = 2 ; for ( $ i = 3 ; $ i * $ i < $ MAXN ; $ i ++ ) { if ( $ spf [ $ i ] == $ i ) { for ( $ j = $ i * $ i ; $ j < $ MAXN ; $ j += $ i ) if ( $ spf [ $ j ] == $ j ) $ spf [ $ j ] = $ i ; } } } function getFactorization ( $ x ) { global $ spf , $ MAXN , $ hash1 ; while ( $ x != 1 ) { $ temp = $ spf [ $ x ] ; if ( $ x % $ temp == 0 ) { $ hash1 [ $ spf [ $ x ] ] ++ ; $ x = ( int ) ( $ x / $ spf [ $ x ] ) ; } while ( $ x % $ temp == 0 ) $ x = ( int ) ( $ x / $ temp ) ; } } function check ( $ x ) { global $ spf , $ MAXN , $ hash1 ; while ( $ x != 1 ) { $ temp = $ spf [ $ x ] ; if ( $ x % $ temp == 0 && $ hash1 [ $ temp ] > 1 ) return false ; while ( $ x % $ temp == 0 ) $ x = ( int ) ( $ x / $ temp ) ; } return true ; } function hasValidNum ( $ arr , $ n ) { global $ spf , $ MAXN , $ hash1 ; sieve ( ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) getFactorization ( $ arr [ $ i ] ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) if ( check ( $ arr [ $ i ] ) ) return true ; return false ; } $ arr = array ( 2 , 8 , 4 , 10 , 6 , 7 ) ; $ n = count ( $ arr ) ; if ( hasValidNum ( $ arr , $ n ) ) echo " Yes " ; else echo " No " ; ? >