Check for an array element that is co | Java 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
class GFG { static int MAXN = 1000001 ; static int [ ] spf = new int [ MAXN ] ; static int [ ] hash1 = new int [ MAXN ] ; static void sieve ( ) { spf [ 1 ] = 1 ; for ( int i = 2 ; i < MAXN ; i ++ ) spf [ i ] = i ; for ( int i = 4 ; i < MAXN ; i += 2 ) spf [ i ] = 2 ; for ( int i = 3 ; i * i < MAXN ; i ++ ) { if ( spf [ i ] == i ) { for ( int j = i * i ; j < MAXN ; j += i ) if ( spf [ j ] == j ) spf [ j ] = i ; } } } static void getFactorization ( int x ) { int temp ; while ( x != 1 ) { temp = spf [ x ] ; if ( x % temp == 0 ) { hash1 [ spf [ x ] ] ++ ; x = x / spf [ x ] ; } while ( x % temp == 0 ) x = x / temp ; } } static boolean check ( int x ) { int temp ; while ( x != 1 ) { temp = spf [ x ] ; if ( x % temp == 0 && hash1 [ temp ] > 1 ) return false ; while ( x % temp == 0 ) x = x / temp ; } return true ; } static boolean hasValidNum ( int [ ] arr , int n ) { sieve ( ) ; for ( int i = 0 ; i < n ; i ++ ) getFactorization ( arr [ i ] ) ; for ( int i = 0 ; i < n ; i ++ ) if ( check ( arr [ i ] ) ) return true ; return false ; } public static void main ( String [ ] args ) { int [ ] arr = { 2 , 8 , 4 , 10 , 6 , 7 } ; int n = arr . length ; if ( hasValidNum ( arr , n ) ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; } }