Check if all the pairs of an array are coprime with each other | C ++ implementation of the above approach ; Function to store and check the factors ; Check if factors are equal ; Check if the factor is already present ; Insert the factor in set ; Check if the factor is already present ; Insert the factors in set ; Function to check if all the pairs of array elements are coprime with each other ; Check if factors of A [ i ] haven 't occurred previously ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool findFactor ( int value , unordered_set < int > & factors ) { factors . insert ( value ) ; for ( int i = 2 ; i * i <= value ; i ++ ) { if ( value % i == 0 ) { if ( value / i == i ) { if ( factors . find ( i ) != factors . end ( ) ) { return true ; } else { factors . insert ( i ) ; } } else { if ( factors . find ( i ) != factors . end ( ) || factors . find ( value / i ) != factors . end ( ) ) { return true ; } else { factors . insert ( i ) ; factors . insert ( value / i ) ; } } } } return false ; } bool allCoprime ( int A [ ] , int n ) { bool all_coprime = true ; unordered_set < int > factors ; for ( int i = 0 ; i < n ; i ++ ) { if ( A [ i ] == 1 ) continue ; if ( findFactor ( A [ i ] , factors ) ) { all_coprime = false ; break ; } } return all_coprime ; } int main ( ) { int A [ ] = { 3 , 5 , 11 , 7 , 19 } ; int arr_size = sizeof ( A ) / sizeof ( A [ 0 ] ) ; if ( allCoprime ( A , arr_size ) ) { cout << " Yes " ; } else { cout << " No " ; } return 0 ; }