Sum of elements in an array having composite frequency | Python3 program to find sum of elements in an array having composite frequency ; Function to create Sieve to check primes ; If composite [ p ] is not changed , then it is a prime ; Update all multiples of p , set them to composite ; Function to return the sum of elements in an array having composite frequency ; Map is used to store element frequencies ; To store sum ; Traverse the map using iterators ; Count the number of elements having composite frequencies ; Driver code ; Function call
N = 100005 NEW_LINE def SieveOfEratosthenes ( composite ) : NEW_LINE INDENT for p in range ( 2 , N ) : NEW_LINE INDENT if p * p > N : NEW_LINE INDENT break NEW_LINE DEDENT if ( composite [ p ] == False ) : NEW_LINE INDENT for i in range ( 2 * p , N , p ) : NEW_LINE INDENT composite [ i ] = True NEW_LINE DEDENT DEDENT DEDENT DEDENT def sumOfElements ( arr , n ) : NEW_LINE INDENT composite = [ False ] * N NEW_LINE SieveOfEratosthenes ( composite ) NEW_LINE m = dict ( ) ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT m [ arr [ i ] ] = m . get ( arr [ i ] , 0 ) + 1 NEW_LINE DEDENT sum = 0 NEW_LINE for it in m : NEW_LINE INDENT if ( composite [ m [ it ] ] ) : NEW_LINE INDENT sum += ( it ) NEW_LINE DEDENT DEDENT return sum NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 1 , 2 , 1 , 1 , 1 , 3 , 3 , 2 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE print ( sumOfElements ( arr , n ) ) NEW_LINE DEDENT