Given an array arr[] of distinct elements, the task is to count the total number of distinct pairs in which at least one element is prime.
Examples:
Input: arr[] = {1, 3, 10, 7, 8}
Output: 7
Pairs with at least one prime are (1, 3), (1, 7),
(3, 1), (3, 7), (3, 8), (10, 7), (7, 8).
Input:arr[]={4, 6, 8, 2, 9};
Output: 4
Approach: First precompute all the prime till the Maximum element of array using Sieve . Traverse each and every possible pair and check if any of the elements in the pair is prime. If yes, then increment the count.
Below is the implementation of above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to find primesvoid sieve(int maxm, int prime[]){ prime[0] = prime[1] = 1; for (int i = 2; i * i <= maxm; i++) if (!prime[i]) for (int j = 2 * i; j <= maxm; j += i) prime[j] = 1;}// Function to count the pairint countPair(int a[], int n){ // Find the maximum element of the array int maxm = *max_element(a, a + n); int prime[maxm + 1]; memset(prime, 0, sizeof(prime)); // Find primes upto maximum sieve(maxm, prime); // Count pairs with at least prime int count = 0; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (prime[a[i]] == 0 || prime[a[j]] == 0) count++; return count;}// Driver codeint main(){ int arr[] = { 2, 3, 5, 4, 7 }; int n = 5; cout << countPair(arr, n); return 0;} |
Java
// Java implementation of the above approachclass GFG{ // Function to find primes static void sieve(int maxm, int prime[]) { prime[0] = prime[1] = 1; for (int i = 2; i * i <= maxm; i++) if (prime[i] == 0) for (int j = 2 * i; j <= maxm; j += i) prime[j] = 1; } // Function to count the pair static int countPair(int a[], int n) { // Find the maximum element of the array int maxm = a[0]; for(int i = 1; i < n; i++) if(a[i] > maxm) maxm = a[i]; int [] prime = new int[maxm + 1]; for(int i = 0; i < maxm + 1; i++) prime[i] = 0; // Find primes upto maximum sieve(maxm, prime); // Count pairs with at least prime int count = 0; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (prime[a[i]] == 0 || prime[a[j]] == 0) count++; return count; } // Driver code public static void main(String []args) { int arr[] = { 2, 3, 5, 4, 7 }; int n = arr.length; System.out.println(countPair(arr, n)); }}// This code is contributed by ihritik |
Python3
# Python 3 implementation of the above approachfrom math import sqrt# Function to count the pairdef countPair(a, n): # Find the maximum element of the array maxm = a[0] for i in range(len(a)): if(a[i] > maxm): maxm = a[i] prime = [0 for i in range(maxm + 1)] # Find primes upto maximum prime[0] = prime[1] = 1; for i in range(2, int(sqrt(maxm)) + 1, 1): if (prime[i] == 0): for j in range(2 * i, maxm + 1, i): prime[j] = 1 # Count pairs with at least prime count = 0 for i in range(n): for j in range(i + 1, n, 1): if (prime[a[i]] == 0 or prime[a[j]] == 0): count += 1 return count# Driver codeif __name__ == '__main__': arr = [2, 3, 5, 4, 7] n = 5 print(countPair(arr, n))# This code is contributed by# Sanjit_Prasad |
C#
// C# implementation of the above approachusing System;class GFG{ // Function to find primes static void sieve(int maxm, int []prime) { prime[0] = prime[1] = 1; for (int i = 2; i * i <= maxm; i++) if (prime[i] == 0) for (int j = 2 * i; j <= maxm; j += i) prime[j] = 1; } // Function to count the pair static int countPair(int []a, int n) { // Find the maximum element of the array int maxm = a[0]; for(int i = 1; i < n; i++) if(a[i] > maxm) maxm = a[i]; int [] prime = new int[maxm + 1]; for(int i = 0; i < maxm + 1; i++) prime[i] = 0; // Find primes upto maximum sieve(maxm, prime); // Count pairs with at least prime int count = 0; for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (prime[a[i]] == 0 || prime[a[j]] == 0) count++; return count; } // Driver code public static void Main() { int []arr = { 2, 3, 5, 4, 7 }; int n = arr.Length; Console.WriteLine(countPair(arr, n)); }}// This code is contributed by ihritik |
PHP
<?php// PHP implementation of the above approach // Function to find primes function sieve($maxm, $prime) { $prime[0] = $prime[1] = 1; for ($i = 2; $i * $i <= $maxm; $i++) if (!$prime[$i]) for ($j = 2 * $i; $j <= $maxm; $j += $i) $prime[$j] = 1; } // Function to count the pair function countPair($a, $n) { // Find the maximum element of the array $maxm = max($a); $prime = array(); $prime = array_fill(0, $maxm + 1, 0); // Find primes upto maximum sieve($maxm, $prime); // Count pairs with at least prime $count = 0; for ($i = 0; $i < $n; $i++) for ($j = $i + 1; $j < $n; $j++) if ($prime[$a[$i]] == 0 || $prime[$a[$j]] == 0) $count++; return $count; } // Driver code $arr = array( 2, 3, 5, 4, 7 ); $n = 5; echo countPair($arr, $n); // This code is contributed by Ryuga?> |
Javascript
<script>// Javascript implementation of the above approach // Function to find primes function sieve(maxm,prime) { prime[0] = prime[1] = 1; for (let i = 2; i * i <= maxm; i++) if (prime[i] == 0) for (let j = 2 * i; j <= maxm; j += i) prime[j] = 1; } // Function to count the pair function countPair(a,n) { // Find the maximum element of the array let maxm = a[0]; for(let i = 1; i < n; i++) if(a[i] > maxm) maxm = a[i]; let prime = new Array(maxm + 1); for(let i = 0; i < maxm + 1; i++) prime[i] = 0; // Find primes upto maximum sieve(maxm, prime); // Count pairs with at least prime let count = 0; for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) if (prime[a[i]] == 0 || prime[a[j]] == 0) count++; return count; } // Driver code let arr=[2, 3, 5, 4, 7]; let n = arr.length; document.write(countPair(arr, n)); // This code is contributed by unknown2108 </script> |
Output
10
Time Complexity: O(max(n2, m*log(log(m)))), where n is the size of the given array and m is the maximum element in the array.
Auxiliary Space: O(m), where m is the maximum element in the array.
Efficient Approach:
Approach: First precompute all the prime till the Maximum element of array using Sieve . Maintain the count of primes and non-primes. Then count pairs with single prime i.e. nonPrimes * Primes and count pairs with both primes (Primes * (Primes – 1)) / 2. Return the sum of both counts.
Below is the implementation of above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>#define ll long long intusing namespace std;// Function to find primesvoid sieve(int maxm, int prime[]){ prime[0] = prime[1] = 1; for (int i = 2; i * i <= maxm; i++) if (!prime[i]) for (int j = 2 * i; j <= maxm; j += i) prime[j] = 1;}ll countPair(int a[], int n){ // Find the maximum element of the array int maxm = *max_element(a, a + n); int prime[maxm + 1]; memset(prime, 0, sizeof(prime)); // Find primes upto maximum sieve(maxm, prime); // Count number of primes int countPrimes = 0; for (int i = 0; i < n; i++) if (prime[a[i]] == 0) countPrimes++; int nonPrimes = n - countPrimes; ll pairswith1Prime = nonPrimes * countPrimes; ll pairsWith2Primes = (countPrimes * (countPrimes - 1)) / 2; return pairswith1Prime + pairsWith2Primes;}// Driver codeint main(){ int arr[] = { 2, 3, 5, 4, 7 }; int n = sizeof(arr) / sizeof(arr[0]); cout << countPair(arr, n); return 0;} |
Java
// Java implementation of the above approachclass GFG{ // Function to find primes static void sieve(int maxm, int []prime) { prime[0] = prime[1] = 1; for (int i = 2; i * i <= maxm; i++) if (prime[i]==0) for (int j = 2 * i; j <= maxm; j += i) prime[j] = 1; } static long countPair(int []a, int n) { // Find the maximum element of the array int maxm = a[0]; int i; for( i = 1; i < n ; i++) if(a[i] > maxm) maxm = a[i]; int [] prime = new int[maxm + 1]; for( i = 0; i < maxm + 1 ;i++) prime[i] = 0; // Find primes upto maximum sieve(maxm, prime); // Count number of primes int countPrimes = 0; for ( i = 0; i < n; i++) if (prime[a[i]] == 0) countPrimes++; int nonPrimes = n - countPrimes; long pairswith1Prime = nonPrimes * countPrimes; long pairsWith2Primes = (countPrimes * (countPrimes - 1)) / 2; return pairswith1Prime + pairsWith2Primes; } // Driver code public static void main(String []args) { int [] arr = { 2, 3, 5, 4, 7 }; int n = arr.length; System.out.println(countPair(arr, n)); }}// This code is contributed by ihritik |
Python3
# Python3 implementation of the above approach# Function to find primesdef sieve(maxm, prime): prime[0] = prime[1] = 1; i = 2; while (i * i <= maxm): if (prime[i] == 0): for j in range(2 * i, maxm + 1, i): prime[j] = 1; i += 1;def countPair(a, n): # Find the maximum element # of the array maxm = max(a); prime = [0] * (maxm + 1); # Find primes upto maximum sieve(maxm, prime); # Count number of primes countPrimes = 0; for i in range(n): if (prime[a[i]] == 0): countPrimes += 1; nonPrimes = n - countPrimes; pairswith1Prime = nonPrimes * countPrimes; pairsWith2Primes = (countPrimes * (countPrimes - 1)) // 2; return pairswith1Prime + pairsWith2Primes;# Driver codearr = [ 2, 3, 5, 4, 7 ];n = len(arr);print(countPair(arr, n));# This code is contributed by mits |
C#
// C# implementation of the above approachusing System;class GFG{ // Function to find primes static void sieve(int maxm, int []prime) { prime[0] = prime[1] = 1; for (int i = 2; i * i <= maxm; i++) if (prime[i] == 0) for (int j = 2 * i; j <= maxm; j += i) prime[j] = 1; } static long countPair(int []a, int n) { // Find the maximum element of the array int maxm = a[0]; int i; for( i = 1; i < n ;i++) if(a[i] > maxm) maxm = a[i]; int [] prime = new int[maxm + 1]; for( i = 0; i < maxm + 1 ;i++) prime[i] = 0; // Find primes upto maximum sieve(maxm, prime); // Count number of primes int countPrimes = 0; for ( i = 0; i < n; i++) if (prime[a[i]] == 0) countPrimes++; int nonPrimes = n - countPrimes; long pairswith1Prime = nonPrimes * countPrimes; long pairsWith2Primes = (countPrimes * (countPrimes - 1)) / 2; return pairswith1Prime + pairsWith2Primes; } // Driver code public static void Main() { int [] arr = { 2, 3, 5, 4, 7 }; int n = arr.Length; Console.WriteLine(countPair(arr, n)); }}// This code is contributed by ihritik |
PHP
<?php// PHP implementation of the above approach// Function to find primesfunction sieve($maxm, $prime){ $prime[0] = $prime[1] = 1; for ($i = 2; $i * $i <= $maxm; $i++) if (!$prime[$i]) for ($j = 2 * $i; $j <= $maxm; $j += $i) $prime[$j] = 1;}function countPair($a, $n){ // Find the maximum element // of the array $maxm = max($a); $prime = array_fill(0, $maxm + 1,0); // Find primes upto maximum sieve($maxm, $prime); // Count number of primes $countPrimes = 0; for ($i = 0; $i < $n; $i++) if ($prime[$a[$i]] == 0) $countPrimes++; $nonPrimes = $n - $countPrimes; $pairswith1Prime = $nonPrimes * $countPrimes; $pairsWith2Primes = ($countPrimes * ($countPrimes - 1)) / 2; return $pairswith1Prime + $pairsWith2Primes;}// Driver code$arr = array( 2, 3, 5, 4, 7 );$n = count($arr);echo countPair($arr, $n);// This code is contributed by mits?> |
Javascript
<script> // JavaScript implementation of the above approach // Function to find primes function sieve(maxm, prime) { prime[0] = prime[1] = 1; for (let i = 2; i * i <= maxm; i++) if (prime[i] == 0) for (let j = 2 * i; j <= maxm; j += i) prime[j] = 1; } function countPair(a, n) { // Find the maximum element of the array let maxm = a[0]; let i; for( i = 1; i < n ;i++) if(a[i] > maxm) maxm = a[i]; let prime = new Array(maxm + 1); for( i = 0; i < maxm + 1 ;i++) prime[i] = 0; // Find primes upto maximum sieve(maxm, prime); // Count number of primes let countPrimes = 0; for ( i = 0; i < n; i++) if (prime[a[i]] == 0) countPrimes++; let nonPrimes = n - countPrimes; let pairswith1Prime = nonPrimes * countPrimes; let pairsWith2Primes = parseInt((countPrimes * (countPrimes - 1)) / 2, 10); return (pairswith1Prime + pairsWith2Primes); } let arr = [ 2, 3, 5, 4, 7 ]; let n = arr.length; document.write(countPair(arr, n)); </script> |
Output
10
Time Complexity: O(max(n, m*log(log(m)))), where n is the size of the given array and m is the maximum element in the array.
Auxiliary Space: O(m), where m is the maximum element in the array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
