Given an array A[] consisting of N positive integers, the task is to check if all the array elements are pairwise co-prime, i.e. for all pairs (Ai , Aj), such that 1<=i<j<=N, GCD(Ai, Aj) = 1.
Examples:
Input : A[] = {2, 3, 5}
Output : Yes
Explanation : All the pairs, (2, 3), (3, 5), (2, 5) are pairwise co-prime.Input : A[] = {5, 10}
Output : No
Explanation : GCD(5, 10)=5 so they are not co-prime.
Naive Approach: The simplest approach to solve the problem is to generate all possible pairs from a given array and for each pair, check if it is coprime or not. If any pair is found to be non-coprime, print “No“. Otherwise, print “Yes“.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following observation:
If any two numbers have a common prime factor, then their GCD can never be 1.
This can also be interpreted as:
The LCM of the array must be equal to the product of the elements in the array.
Therefore, the solution boils down to calculating the LCM of the given array and check if it is equal to the product of all the array elements or not.
Below is the implementation of the above approach :
C++
// C++ Program for the above approach #include <bits/stdc++.h> using namespace std; #define ll long long int // Function to calculate GCD ll GCD(ll a, ll b) { if (a == 0) return b; return GCD(b % a, a); } // Function to calculate LCM ll LCM(ll a, ll b) { return (a * b) / GCD(a, b); } // Function to check if all elements // in the array are pairwise coprime void checkPairwiseCoPrime(int A[], int n) { // Initialize variables ll prod = 1; ll lcm = 1; // Iterate over the array for (int i = 0; i < n; i++) { // Calculate product of // array elements prod *= A[i]; // Calculate LCM of // array elements lcm = LCM(A[i], lcm); } // If the product of array elements // is equal to LCM of the array if (prod == lcm) cout << "Yes" << endl; else cout << "No" << endl; } // Driver Code int main() { int A[] = { 2, 3, 5 }; int n = sizeof(A) / sizeof(A[0]); // Function call checkPairwiseCoPrime(A, n); } |
Java
// Java program for the above approachimport java.util.*;import java.lang.*;class GFG{// Function to calculate GCD static long GCD(long a, long b) { if (a == 0) return b; return GCD(b % a, a); } // Function to calculate LCM static long LCM(long a, long b) { return (a * b) / GCD(a, b); } // Function to check if all elements // in the array are pairwise coprime static void checkPairwiseCoPrime(int A[], int n) { // Initialize variables long prod = 1; long lcm = 1; // Iterate over the array for(int i = 0; i < n; i++) { // Calculate product of // array elements prod *= A[i]; // Calculate LCM of // array elements lcm = LCM(A[i], lcm); } // If the product of array elements // is equal to LCM of the array if (prod == lcm) System.out.println("Yes"); else System.out.println("No"); }// Driver Codepublic static void main (String[] args){ int A[] = { 2, 3, 5 }; int n = A.length; // Function call checkPairwiseCoPrime(A, n); }}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach # Function to calculate GCD def GCD(a, b): if (a == 0): return b return GCD(b % a, a) # Function to calculate LCM def LCM(a, b): return (a * b) // GCD(a, b) # Function to check if aelements # in the array are pairwise coprime def checkPairwiseCoPrime(A, n): # Initialize variables prod = 1 lcm = 1 # Iterate over the array for i in range(n): # Calculate product of # array elements prod *= A[i] # Calculate LCM of # array elements lcm = LCM(A[i], lcm) # If the product of array elements # is equal to LCM of the array if (prod == lcm): print("Yes") else: print("No") # Driver Code if __name__ == '__main__': A = [ 2, 3, 5 ] n = len(A) # Function call checkPairwiseCoPrime(A, n) # This code is contributed by mohit kumar 29 |
C#
// C# program for // the above approachusing System;using System.Collections.Generic;class GFG{// Function to calculate GCD static long GCD(long a, long b) { if (a == 0) return b; return GCD(b % a, a); } // Function to calculate LCM static long LCM(long a, long b) { return (a * b) / GCD(a, b); } // Function to check if all elements // in the array are pairwise coprime static void checkPairwiseCoPrime(int []A, int n) { // Initialize variables long prod = 1; long lcm = 1; // Iterate over the array for(int i = 0; i < n; i++) { // Calculate product of // array elements prod *= A[i]; // Calculate LCM of // array elements lcm = LCM(A[i], lcm); } // If the product of array elements // is equal to LCM of the array if (prod == lcm) Console.WriteLine("Yes"); else Console.WriteLine("No"); }// Driver Codepublic static void Main(String[] args){ int []A = {2, 3, 5}; int n = A.Length; // Function call checkPairwiseCoPrime(A, n); }}// This code is contributed by Rajput-Ji |
Javascript
<script>// javascript program for the above approach // Function to calculate GCD function GCD(a , b) { if (a == 0) return b; return GCD(b % a, a); } // Function to calculate LCM function LCM(a , b) { return (a * b) / GCD(a, b); } // Function to check if all elements // in the array are pairwise coprime function checkPairwiseCoPrime(A , n) { // Initialize variables var prod = 1; var lcm = 1; // Iterate over the array for (i = 0; i < n; i++) { // Calculate product of // array elements prod *= A[i]; // Calculate LCM of // array elements lcm = LCM(A[i], lcm); } // If the product of array elements // is equal to LCM of the array if (prod == lcm) document.write("Yes"); else document.write("No"); } // Driver Code var A = [ 2, 3, 5 ]; var n = A.length; // Function call checkPairwiseCoPrime(A, n);// This code contributed by umadevi9616</script> |
Yes
Time Complexity: O(N log (min(A[i])))
Auxiliary Space: O(1)
Approach#2:using nested loop
Algorithm
1. Define a function named are_elements_pairwise_coprime that takes an array arr as input.
2.Initialize a variable n to the length of the array arr.
3.Loop over all pairs of elements in the array using nested loops, i.e., for each element arr[i], loop over all elements arr[j] where j > i.
4.For each pair of elements, compute their GCD using the gcd function defined below.
5.If the GCD of any pair of elements is not equal to 1, return “No”.
6.If all pairs of elements have a GCD equal to 1, return “Yes”.
Python3
def are_elements_pairwise_coprime(arr): n = len(arr) for i in range(n): for j in range(i+1, n): if gcd(arr[i], arr[j]) != 1: return "No" return "Yes"def gcd(a, b): if b == 0: return a else: return gcd(b, a % b)arr= [2, 3, 5]print(are_elements_pairwise_coprime(arr)) |
Yes
The time complexity of this algorithm is O(n^2), where n is the length of the input array, since we are checking all possible pairs of elements.
The space complexity is O(1), since we are not using any additional data structures.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
