Find the array element having equal sum of Prime Numbers on its left and right | Python3 program for the above approach ; Function to find an index in the array having sum of prime numbers to its left and right equal ; Stores the maximum value present in the array ; Stores all positive elements which are <= max_value ; If 1 is present ; Remove 1 ; Sieve of Eratosthenes to store all prime numbers which are <= max_value in the Map ; Erase non - prime numbers ; Stores the sum of prime numbers from left ; Stores the sum of prime numbers to the left of each index ; Stores the sum of prime numbers to the left of the current index ; Add current value to the prime sum if the current value is prime ; Stores the sum of prime numbers from right ; Stores the sum of prime numbers to the right of each index ; Stores the sum of prime numbers to the right of the current index ; Add current value to the prime sum if the current value is prime ; Traverse through the two arrays to find the index ; Compare the values present at the current index ; Return the index where both the values are same ; No index is found . ; Driver Code ; Given array arr [ ] ; Size of Array ; Function Call
from math import sqrt NEW_LINE def find_index ( arr , N ) : NEW_LINE INDENT max_value = - 10 ** 9 NEW_LINE for i in range ( N ) : NEW_LINE INDENT max_value = max ( max_value , arr [ i ] ) NEW_LINE DEDENT store = { } NEW_LINE for i in range ( 1 , max_value + 1 ) : NEW_LINE INDENT store [ i ] = store . get ( i , 0 ) + 1 NEW_LINE DEDENT if ( 1 in store ) : NEW_LINE INDENT del store [ 1 ] NEW_LINE DEDENT for i in range ( 2 , int ( sqrt ( max_value ) ) + 1 ) : NEW_LINE INDENT multiple = 2 NEW_LINE while ( ( i * multiple ) <= max_value ) : NEW_LINE INDENT if ( i * multiple in store ) : NEW_LINE INDENT del store [ i * multiple ] NEW_LINE DEDENT multiple += 1 NEW_LINE DEDENT DEDENT prime_sum_from_left = 0 NEW_LINE first_array = [ 0 ] * N NEW_LINE for i in range ( N ) : NEW_LINE INDENT first_array [ i ] = prime_sum_from_left NEW_LINE if arr [ i ] in store : NEW_LINE INDENT prime_sum_from_left += arr [ i ] NEW_LINE DEDENT DEDENT prime_sum_from_right = 0 NEW_LINE second_array = [ 0 ] * N NEW_LINE for i in range ( N - 1 , - 1 , - 1 ) : NEW_LINE INDENT second_array [ i ] = prime_sum_from_right NEW_LINE if ( arr [ i ] in store ) : NEW_LINE INDENT prime_sum_from_right += arr [ i ] NEW_LINE DEDENT DEDENT for i in range ( N ) : NEW_LINE INDENT if ( first_array [ i ] == second_array [ i ] ) : NEW_LINE INDENT return i NEW_LINE DEDENT DEDENT return - 1 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 11 , 4 , 7 , 6 , 13 , 1 , 5 ] NEW_LINE N = len ( arr ) NEW_LINE print ( find_index ( arr , N ) ) NEW_LINE DEDENT