Question

Write a python program to sum the prime numbers existing in an array . For instance , if A = [4, 7, 12, 3, 9] the output should be 10

Answer 1

This can be done using two methods
1st - we go through the given array and one by one check if each number is prime or not.
2nd - this is the efficient solution and the one we will implement.
In this method , we will find the max value in our array then we create a new boolean array prime[0..max]. All the prime numbers in this array will have True value and rest of them will have false.
Now we traverse the array and find the sum of prime numbers using our newly created array.

def primeSum(arr):
    n=len(arr)
    maxVal = max(arr)    # find the maximum value in our array
# create a Boolean array prime[0....max_val], this contains status of all the numbers from 0 to maximum value in array. If the specific number is prime the value in the array will be true else it will be false.
    prime=[True for i in range(maxVal + 1)] #creating the array
#0 and 1 are not prime so setting them to false 
#you might think we don't need these two numbers so why add them ? This is so that their location can match there value. Eg. In this array the value 2 is at location 2, 3 is at location 3 and so on.
# this way we can access the array easily. Eg. To check if 7 is prime we can do prime[7] and this will return True.
    prime[0] = False 
    prime[1] = False
# now changing the status of rest of the numbers here we take the first prime and change values of its multiples to false. Eg. We see 2 is prime so we change values of number 4,6,8.... To False in the array.Similary next number is 3 and its multiple 9,12,15,18.... will be set to False and so on
    for p in range(2, maxVal + 1): 
        if(p * p > maxVal):       # we only need to change the values until this holds as the rest of the array will be set automatically
            break
        if (prime[p] == True):
            for i in range(p * 2, maxVal+1, p): 
                prime[i] = False
# Now we calculate the sum of all prime numbers in our array. For a number in our array we check if the number is prime or not using the prime array we created.
    sum = 0 
    for i in range(n): 
        if (prime[arr[i]]): 
            sum += arr[i] 
    return sum
    
    
arr =[4,7,12,3,9]
print(primeSum(arr))

Output - 10