Count pairs in an array whose product is composite number
Given an array, arr[] of size N, the task is to count all the pairs of the given array whose product is a composite number.
Examples:
Input: arr[] = {1, 4, 7}
Output: 2
Explanation:
Pairs whose product is a composite number are:(4, 7), (1, 4).
Therefore, the required output is 2.Input: arr[] = {1, 2, 8, 10}
Output: 5
Naive approach: The idea is to traverse the array and generate all the possible pairs of the given array. For each pair, check if the product of its elements is a composite number or not. If found to be true, then increment the count by 1. Follow the steps below to solve the problem:
- Initialize a variable, say res to store the count of pairs whose product is a composite number.
- Traverse the array and generate all possible pairs of the given array.
- For each pair, check if their product is composite or not. If found to be true, then increment the value of res by 1.
- Finally, print the value of res.
Below is the implementation of the above approach
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to check if a // number is prime or not bool isComposite( int N) { // Check if N is multiple // of i or not. for ( int i = 2; i * i <= N; i++) { // If N is multiple of i. if (N % i == 0) { return true ; } } return false ; } // Function to get the count // of pairs whose product // is a composite number. int compositePair( int arr[], int N) { // Stores the count of pairs // whose product is // a composite number int res = 0; // Generate all possible pairs for ( int i = 0; i < N; i++) { for ( int j = i + 1; j < N; j++) { // Stores the product of // element of current pair int prod = arr[i] * arr[j]; // If prod is a // composite number if (isComposite(prod)) { res++; } } } return res; } // Driver Code int main() { int arr[] = { 1, 1, 2, 2, 8 }; int N = sizeof (arr) / sizeof (arr[0]); cout << compositePair(arr, N); return 0; } |
Java
// Java Program to implement // the above approach import java.io.*; class GFG{ // Function to check if a // number is prime or not static boolean isComposite( int N) { // Check if N is multiple // of i or not. for ( int i = 2 ; i * i <= N; i++) { // If N is multiple of i. if (N % i == 0 ) { return true ; } } return false ; } // Function to get the count // of pairs whose product // is a composite number. static int compositePair( int arr[], int N) { // Stores the count of pairs // whose product is // a composite number int res = 0 ; // Generate all possible pairs for ( int i = 0 ; i < N; i++) { for ( int j = i + 1 ; j < N; j++) { // Stores the product of // element of current pair int prod = arr[i] * arr[j]; // If prod is a // composite number if (isComposite(prod)) { res++; } } } return res; } // Driver Code public static void main (String[] args) { int arr[] = { 1 , 1 , 2 , 2 , 8 }; int N = arr.length; System.out.println(compositePair(arr, N)); } } // This code is contributed by sanjoy_62 |
Python3
# Python3 program to implement # the above approach # Function to check if a # number is prime or not def isComposite(N): # Check if N is multiple # of i or not. for i in range ( 2 , N + 1 ): if i * i > N: break # If N is multiple of i. if (N % i = = 0 ): return True return False # Function to get the count # of pairs whose product # is a composite number. def compositePair(arr, N): # Stores the count of pairs # whose product is # a composite number res = 0 # Generate all possible pairs for i in range (N): for j in range (i + 1 , N): # Stores the product of # element of current pair prod = arr[i] * arr[j] # If prod is a # composite number if (isComposite(prod)): res + = 1 return res # Driver Code if __name__ = = '__main__' : arr = [ 1 , 1 , 2 , 2 , 8 ] N = len (arr) print (compositePair(arr, N)) # This code is contributed by mohit kumar 29 |
C#
// C# Program to implement // the above approach using System; class GFG{ // Function to check if a // number is prime or not static bool isComposite( int N) { // Check if N is multiple // of i or not. for ( int i = 2; i * i <= N; i++) { // If N is multiple of i. if (N % i == 0) { return true ; } } return false ; } // Function to get the count // of pairs whose product // is a composite number. static int compositePair( int []arr, int N) { // Stores the count of pairs // whose product is // a composite number int res = 0; // Generate all possible pairs for ( int i = 0; i < N; i++) { for ( int j = i + 1; j < N; j++) { // Stores the product of // element of current pair int prod = arr[i] * arr[j]; // If prod is a // composite number if (isComposite(prod)) { res++; } } } return res; } // Driver Code public static void Main(String[] args) { int []arr = {1, 1, 2, 2, 8}; int N = arr.Length; Console.WriteLine(compositePair(arr, N)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // Javascript program to implement // the above approach // Function to check if a // number is prime or not function isComposite(N) { var i; // Check if N is multiple // of i or not. for (i = 2; i * i <= N; i++) { // If N is multiple of i. if (N % i == 0) { return true ; } } return false ; } // Function to get the count // of pairs whose product // is a composite number. function compositePair(arr, N) { // Stores the count of pairs // whose product is // a composite number var res = 0; var i,j; // Generate all possible pairs for (i = 0; i < N; i++) { for (j = i + 1; j < N; j++) { // Stores the product of // element of current pair var prod = arr[i] * arr[j]; // If prod is a // composite number if (isComposite(prod)) { res++; } } } return res; } // Driver Code var arr = [1, 1, 2, 2, 8]; var N = arr.length; document.write(compositePair(arr, N)); </script> |
5
Time Complexity: O(N2 √X), where X is the maximum possible product of a pair in the given array.
Auxiliary Space: O(1)
Efficient Approach: TO optimize the above approach, the idea is to use the fact that all the prime numbers and 1s are not composite numbers. Follow the steps below to solve the problem:
- Initialize two variables cntPrime and cntOne to store the count of 1s and prime numbers in the given array respectively.
- Initialize a variable, say res to store the count of pairs whose product is a composite number.
- Total pairs whose product is not a composite number is:
cntNonComp = cntPrime × cntOne + cntOne × (cntOne – 1) / 2.
- Therefore, the total count of pairs whose product is a composite number is:
res = N × (N – 1) / 2 – cntNonComp.
- Finally, print the value of res.
Below is the implementation of the above approach
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; #define X 1000000 // Function to get all // the prime numbers in // the range[1, X] vector< bool > getPrimeNum() { // Stores the boolean value // to check if a number is // prime or not vector< bool > isPrime(X, true ); isPrime[0] = false ; isPrime[1] = false ; // Mark all non prime // numbers as false for ( int i = 2; i * i <= X; i++) { // If i is prime number if (isPrime[i] == true ) { for ( int j = i * i; j < X; j += i) { // Mark j as // a composite number isPrime[j] = false ; } } } return isPrime; } // Function to get the count of pairs // whose product is a composite number int cntPairs( int arr[], int N) { // Stores the boolean value // to check if a number is // prime or not vector< bool > isPrime = getPrimeNum(); // Stores the count of 1s int cntOne = 0; // Stores the count // of prime numbers int cntPrime = 0; // Traverse the given array. for ( int i = 0; i < N; i++) { if (arr[i] == 1) { cntOne += 1; } else if (isPrime[i]) { cntPrime += 1; } } // Stores count of pairs whose // product is not a composite number int cntNonComp = 0; cntNonComp = cntPrime * cntOne + cntOne * (cntOne - 1) / 2; // Stores the count of pairs // whose product is composite number int res = 0; res = N * (N - 1) / 2 - cntNonComp; return res; } // Driver Code int main() { int arr[] = { 1, 1, 2, 2, 8 }; int N = sizeof (arr) / sizeof (arr[0]); cout << cntPairs(arr, N); } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ public static int X = 1000000 ; // Function to get all // the prime numbers in // the range[1, X] public static boolean [] getPrimeNum() { // Stores the boolean value // to check if a number is // prime or not boolean isPrime[] = new boolean [X]; Arrays.fill(isPrime, true ); isPrime[ 0 ] = false ; isPrime[ 1 ] = false ; // Mark all non prime // numbers as false for ( int i = 2 ; i * i <= X; i++) { // If i is prime number if (isPrime[i] == true ) { for ( int j = i * i; j < X; j += i) { // Mark j as a composite // number isPrime[j] = false ; } } } return isPrime; } // Function to get the count of pairs // whose product is a composite number public static int cntPairs( int arr[], int N) { // Stores the boolean value // to check if a number is // prime or not boolean isPrime[] = getPrimeNum(); // Stores the count of 1s int cntOne = 0 ; // Stores the count // of prime numbers int cntPrime = 0 ; // Traverse the given array. for ( int i = 0 ; i < N; i++) { if (arr[i] == 1 ) { cntOne += 1 ; } else if (isPrime[i]) { cntPrime += 1 ; } } // Stores count of pairs whose // product is not a composite number int cntNonComp = 0 ; cntNonComp = cntPrime * cntOne + cntOne * (cntOne - 1 ) / 2 ; // Stores the count of pairs // whose product is composite number int res = 0 ; res = N * (N - 1 ) / 2 - cntNonComp; return res; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 1 , 2 , 2 , 8 }; int N = arr.length; System.out.println(cntPairs(arr, N)); } } // This code is contributed by divyeshrabadiya07 |
Python3
# Python3 program to implement # the above approach X = 1000000 # Function to get all # the prime numbers in # the range[1, X] def getPrimeNum(): # Stores the boolean value # to check if a number is # prime or not isPrime = [ True ] * (X) isPrime[ 0 ] = False isPrime[ 1 ] = False # Mark all non prime # numbers as false i = 2 while i * i < = X: # If i is prime number if (isPrime[i] = = True ): for j in range (i * i, X, i): # Mark j as # a composite number isPrime[j] = False i + = 1 return isPrime # Function to get the count # of pairs whose product # is a composite number def cntPairs(arr, N): # Stores the boolean value # to check if a number is # prime or not isPrime = getPrimeNum() # Stores the count of 1s cntOne = 0 # Stores the count # of prime numbers cntPrime = 0 # Traverse the given array. for i in range (N): if (arr[i] = = 1 ): cntOne + = 1 elif (isPrime[i]): cntPrime + = 1 # Stores count of pairs whose # product is not a composite number cntNonComp = 0 cntNonComp = (cntPrime * cntOne + cntOne * (cntOne - 1 ) / / 2 ) # Stores the count of pairs # whose product is composite number res = 0 res = (N * (N - 1 ) / / 2 - cntNonComp) return res # Driver Code if __name__ = = "__main__" : arr = [ 1 , 1 , 2 , 2 , 8 ] N = len (arr) print (cntPairs(arr, N)) # This code is contributed by Chitranayal |
C#
// C# program to implement // the above approach using System; class GFG{ public static int X = 1000000; // Function to get all // the prime numbers in // the range[1, X] public static bool [] getPrimeNum() { // Stores the bool value // to check if a number is // prime or not bool []isPrime = new bool [X]; for ( int i = 0; i < X; i++) isPrime[i] = true ; isPrime[0] = false ; isPrime[1] = false ; // Mark all non prime // numbers as false for ( int i = 2; i * i <= X; i++) { // If i is prime number if (isPrime[i] == true ) { for ( int j = i * i; j < X; j += i) { // Mark j as a composite // number isPrime[j] = false ; } } } return isPrime; } // Function to get the count of pairs // whose product is a composite number public static int cntPairs( int []arr, int N) { // Stores the bool value // to check if a number is // prime or not bool []isPrime = getPrimeNum(); // Stores the count of 1s int cntOne = 0; // Stores the count // of prime numbers int cntPrime = 0; // Traverse the given array. for ( int i = 0; i < N; i++) { if (arr[i] == 1) { cntOne += 1; } else if (isPrime[i]) { cntPrime += 1; } } // Stores count of pairs // whose product is not // a composite number int cntNonComp = 0; cntNonComp = cntPrime * cntOne + cntOne * (cntOne - 1) / 2; // Stores the count of pairs // whose product is composite number int res = 0; res = N * (N - 1) / 2 - cntNonComp; return res; } // Driver code public static void Main(String[] args) { int []arr = {1, 1, 2, 2, 8}; int N = arr.Length; Console.WriteLine(cntPairs(arr, N)); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // Js program to implement // the above approach let X = 1000000; // Function to get all // the prime numbers in // the range[1, X] function getPrimeNum() { // Stores the boolean value // to check if a number is // prime or not let prime = []; for (let i = 0; i<X; i++){ prime.push( true ); } prime[0] = false ; prime[1] = false ; for (let p = 2; p * p <= prime.length; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for (let i = p * 2; i <= prime.length; i += p) prime[i] = false ; } } return prime; } // Function to get the count of pairs // whose product is a composite number function cntPairs( arr, N) { // Stores the boolean value // to check if a number is // prime or not let isPrime = getPrimeNum(); // Stores the count of 1s let cntOne = 0; // Stores the count // of prime numbers let cntPrime = 0; // Traverse the given array. for (let i = 0; i < N; i++) { if (arr[i] == 1) { cntOne += 1; } else if (isPrime[i]) { cntPrime += 1; } } // Stores count of pairs whose // product is not a composite number let cntNonComp = 0; cntNonComp = cntPrime * cntOne + Math.floor(cntOne * (cntOne - 1) / 2); // Stores the count of pairs // whose product is composite number let res = 0; res = N *Math.floor( (N - 1) / 2) - cntNonComp; return res; } // Driver Code let arr = [ 1, 1, 2, 2, 8 ]; let N = arr.length; document.write( cntPairs(arr, N)); </script> |
5
Time Complexity: O(N + X × log(log(X))), Where X stores the maximum possible product of a pair in the given array.
Auxiliary Space: O(X)