Sum of all prime numbers in an Array
Given an array arr[] of N positive integers. The task is to write a program to find the sum of all prime elements in the given array.
Examples:
Input: arr[] = {1, 3, 4, 5, 7}
Output: 15
There are three primes, 3, 5 and 7 whose sum =15.Input: arr[] = {1, 2, 3, 4, 5, 6, 7}
Output: 17
Naive Approach: A simple solution is to traverse the array and keep checking for every element if it is prime or not and add the prime element at the same time.
Efficient Approach: Generate all primes up to the maximum element of the array using the sieve of Eratosthenes and store them in a hash. Now traverse the array and find the sum of those elements which are prime using the sieve.
Below is the implementation of the efficient approach:
C++
// CPP program to find sum of // primes in given array. #include <bits/stdc++.h> using namespace std; // Function to find count of prime int primeSum( int arr[], int n) { // Find maximum value in the array int max_val = *max_element(arr, arr + n); // USE SIEVE TO FIND ALL PRIME NUMBERS LESS // THAN OR EQUAL TO max_val // Create a boolean array "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. vector< bool > prime(max_val + 1, true ); // Remaining part of SIEVE prime[0] = false ; prime[1] = false ; for ( int p = 2; p * p <= max_val; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true ) { // Update all multiples of p for ( int i = p * 2; i <= max_val; i += p) prime[i] = false ; } } // Sum all primes in arr[] int sum = 0; for ( int i = 0; i < n; i++) if (prime[arr[i]]) sum += arr[i]; return sum; } // Driver code int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = sizeof (arr) / sizeof (arr[0]); cout << primeSum(arr, n); return 0; } |
Java
// Java program to find sum of // primes in given array. import java.util.*; class GFG { // Function to find count of prime static int primeSum( int arr[], int n) { // Find maximum value in the array int max_val = Arrays.stream(arr).max().getAsInt(); // USE SIEVE TO FIND ALL PRIME NUMBERS LESS // THAN OR EQUAL TO max_val // Create a boolean array "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. Vector<Boolean> prime = new Vector<>(max_val + 1 ); for ( int i = 0 ; i < max_val + 1 ; i++) prime.add(i,Boolean.TRUE); // Remaining part of SIEVE prime.add( 0 ,Boolean.FALSE); prime.add( 1 ,Boolean.FALSE); for ( int p = 2 ; p * p <= max_val; p++) { // If prime[p] is not changed, then // it is a prime if (prime.get(p) == true ) { // Update all multiples of p for ( int i = p * 2 ; i <= max_val; i += p) prime.add(i,Boolean.FALSE); } } // Sum all primes in arr[] int sum = 0 ; for ( int i = 0 ; i < n; i++) if (prime.get(arr[i])) sum += arr[i]; return sum; } // Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 }; int n = arr.length; System.out.print(primeSum(arr, n)); } } /* This code contributed by PrinciRaj1992 */ |
Python
# Python3 program to find sum of # primes in given array. # Function to find count of prime def primeSum( arr, n): # Find maximum value in the array max_val = max (arr) # USE SIEVE TO FIND ALL PRIME NUMBERS LESS # THAN OR EQUAL TO max_val # Create a boolean array "prime[0..n]". A # value in prime[i] will finally be False # if i is Not a prime, else true. prime = [ True for i in range (max_val + 1 )] # Remaining part of SIEVE prime[ 0 ] = False prime[ 1 ] = False for p in range ( 2 , max_val + 1 ): if (p * p > max_val): break # If prime[p] is not changed, then # it is a prime if (prime[p] = = True ): # Update all multiples of p for i in range (p * 2 , max_val + 1 , p): prime[i] = False # Sum all primes in arr[] sum = 0 for i in range (n): if (prime[arr[i]]): sum + = arr[i] return sum # Driver code arr = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] n = len (arr) print (primeSum(arr, n)) # This code is contributed by mohit kumar 29 |
C#
// C# program to find sum of // primes in given array. using System; using System.Linq; using System.Collections.Generic; class GFG { // Function to find count of prime static int primeSum( int []arr, int n) { // Find maximum value in the array int max_val = arr.Max(); // USE SIEVE TO FIND ALL PRIME NUMBERS LESS // THAN OR EQUAL TO max_val // Create a boolean array "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. List< bool > prime = new List< bool >(max_val + 1); for ( int i = 0; i < max_val + 1; i++) prime.Insert(i, true ); // Remaining part of SIEVE prime.Insert(0, false ); prime.Insert(1, false ); for ( int p = 2; p * p <= max_val; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true ) { // Update all multiples of p for ( int i = p * 2; i <= max_val; i += p) prime.Insert(i, false ); } } // Sum all primes in arr[] int sum = 0; for ( int i = 0; i < n; i++) if (prime[arr[i]]) sum += arr[i]; return sum; } // Driver code public static void Main(String[] args) { int []arr = { 1, 2, 3, 4, 5, 6, 7 }; int n = arr.Length; Console.WriteLine(primeSum(arr, n)); } } // This code contributed by Rajput-Ji |
Javascript
<script> // Javascript program to find sum of // primes in given array. // Function to find count of prime function primeSum(arr, n) { // Find maximum value in the array let max_val = arr.sort((a, b) => b - a)[0]; // USE SIEVE TO FIND ALL PRIME NUMBERS LESS // THAN OR EQUAL TO max_val // Create a boolean array "prime[0..n]". A // value in prime[i] will finally be false // if i is Not a prime, else true. let prime = new Array(max_val + 1).fill( true ); // Remaining part of SIEVE prime[0] = false ; prime[1] = false ; for (let p = 2; p * p <= max_val; p++) { // If prime[p] is not changed, then // it is a prime if (prime[p] == true ) { // Update all multiples of p for (let i = p * 2; i <= max_val; i += p) prime[i] = false ; } } // Sum all primes in arr[] let sum = 0; for (let i = 0; i < n; i++) if (prime[arr[i]]) sum += arr[i]; return sum; } // Driver code let arr = [1, 2, 3, 4, 5, 6, 7]; let n = arr.length; document.write(primeSum(arr, n)); // This code is contributed by _saurabh_jaiswal. </script> |
17
Time complexity: O(M*loglogM) (where, M = maximum element present in arr)
Auxiliary Space: O(M), for the extra vector used. (where, M = maximum element present in arr)
Contact Us