Given two arrays arr1[] and arr2[]. The task is to count the distinct sums that can be obtained while choosing a prime element from arr1[] and another prime element from arr2[].
Examples:
Input: arr1[] = {2, 3}, arr2[] = {2, 2, 4, 7}
Output: 4
All possible prime pairs are (2, 2), (2, 2), (2, 7), (3, 2), (3, 2)
and (3, 7) with sums 4, 4, 9, 5, 5 and 10 respectively.
Input: arr1[] = {3, 1, 4, 2, 5}, arr2[] = {8, 7, 10, 6, 5}
Output: 5
Approach: Use Sieve of Eratosthenes to check whether a number is prime or not then for every prime pair, store it’s sum in a set in order to avoid duplicates. The size of the final set will be the required answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>#define MAX 1000000using namespace std;bool prime[MAX];void sieve(){ memset(prime, true, sizeof(prime)); prime[0] = prime[1] = false; for (int p = 2; p * p <= MAX; p++) { if (prime[p] == true) { for (int i = p * p; i <= MAX; i += p) prime[i] = false; } }}// Function to return the distinct sums// that can be obtained by adding prime// numbers from the given arraysint distinctSum(int arr1[], int arr2[], int m, int n){ sieve(); // Set to store distinct sums set<int, greater<int> > sumSet; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (prime[arr1[i]] && prime[arr2[j]]) sumSet.insert(arr1[i] + arr2[j]); return sumSet.size();}// Driver codeint main(){ int arr1[] = { 2, 3 }; int arr2[] = { 2, 2, 4, 7 }; int m = sizeof(arr1) / sizeof(arr1[0]); int n = sizeof(arr2) / sizeof(arr2[0]); cout << distinctSum(arr1, arr2, m, n); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{static int MAX = 1000000;static boolean []prime = new boolean[MAX + 1];static void sieve(){ Arrays.fill(prime, true); prime[0] = prime[1] = false; for (int p = 2; p * p <= MAX; p++) { if (prime[p] == true) { for (int i = p * p; i <= MAX; i += p) prime[i] = false; } }}// Function to return the distinct sums// that can be obtained by adding prime// numbers from the given arraysstatic int distinctSum(int arr1[], int arr2[], int m, int n){ sieve(); // Set to store distinct sums Set<Integer> sumSet = new HashSet<Integer>(); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (prime[arr1[i]] && prime[arr2[j]]) sumSet.add(arr1[i] + arr2[j]); return sumSet.size();}// Driver codepublic static void main(String[] args){ int arr1[] = { 2, 3 }; int arr2[] = { 2, 2, 4, 7 }; int m = arr1.length; int n = arr2.length; System.out.println(distinctSum(arr1, arr2, m, n));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approachMAX = 1000000prime = [True for i in range(MAX + 1)]def sieve(): prime[0], prime[1] = False, False for p in range(2, MAX + 1): if p * p > MAX: break if (prime[p] == True): for i in range(2 * p, MAX + 1, p): prime[i] = False# Function to return the distinct sums# that can be obtained by adding prime# numbers from the given arraysdef distinctSum(arr1, arr2, m, n): sieve() # Set to store distinct sums sumSet = dict() for i in range(m): for j in range(n): if (prime[arr1[i]] and prime[arr2[j]]): sumSet[arr1[i] + arr2[j]] = 1 return len(sumSet)# Driver codearr1 = [2, 3 ]arr2 = [2, 2, 4, 7 ]m = len(arr1)n = len(arr2)print(distinctSum(arr1, arr2, m, n))# This code is contributed by mohit kumar |
C#
// C# implementation of the approach using System;using System.Collections.Generic;class GFG{static int MAX = 1000000;static bool []prime = new bool[MAX + 1];static void sieve(){ for (int i = 0; i < MAX + 1; i++) prime[i] = true; prime[0] = prime[1] = false; for (int p = 2; p * p <= MAX; p++) { if (prime[p] == true) { for (int i = p * p; i <= MAX; i += p) prime[i] = false; } }}// Function to return the distinct sums// that can be obtained by adding prime// numbers from the given arraysstatic int distinctSum(int []arr1, int []arr2, int m, int n){ sieve(); // Set to store distinct sums HashSet<int> sumSet = new HashSet<int>(); for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (prime[arr1[i]] && prime[arr2[j]]) sumSet.Add(arr1[i] + arr2[j]); return sumSet.Count;}// Driver codepublic static void Main(String[] args){ int []arr1 = { 2, 3 }; int []arr2 = { 2, 2, 4, 7 }; int m = arr1.Length; int n = arr2.Length; Console.WriteLine(distinctSum(arr1, arr2, m, n));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript implementation of the approachlet MAX = 1000000let prime = new Array(MAX);function sieve() { prime.fill(true) prime[0] = prime[1] = false; for (let p = 2; p * p <= MAX; p++) { if (prime[p] == true) { for (let i = p * p; i <= MAX; i += p) prime[i] = false; } }}// Function to return the distinct sums// that can be obtained by adding prime// numbers from the given arraysfunction distinctSum(arr1, arr2, m, n) { sieve(); // Set to store distinct sums let sumSet = new Set(); for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) if (prime[arr1[i]] && prime[arr2[j]]) sumSet.add(arr1[i] + arr2[j]); return sumSet.size;}// Driver codelet arr1 = [2, 3];let arr2 = [2, 2, 4, 7];let m = arr1.length;let n = arr2.length;document.write(distinctSum(arr1, arr2, m, n));// This code is contributed by _saurabh_jaiswal</script> |
Output:
4
Time Complexity : O(N * M * log (N * M) + MAX * log(MAX) )
Auxiliary Space: O(MAX + N * M)
