text: Sum of elements in an array having composite frequency | C ++ 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  100005 NEW_LINE void SieveOfEratosthenes ( vector < bool > & composite ) { for ( int i = 0 ; i < N ; i ++ ) composite [ i ] = false ; for ( int p = 2 ; p * p < N ; p ++ ) { if ( ! composite [ p ] ) { for ( int i = p * 2 ; i < N ; i += p ) composite [ i ] = true ; } } } int sumOfElements ( int arr [ ] , int n ) { vector < bool > composite ( N ) ; SieveOfEratosthenes ( composite ) ; unordered_map < int , int > m ; for ( int i = 0 ; i < n ; i ++ ) m [ arr [ i ] ] ++ ; int sum = 0 ; for ( auto it = m . begin ( ) ; it != m . end ( ) ; it ++ ) { if ( composite [ it -> second ] ) { sum += ( it -> first ) ; } } return sum ; } int main ( ) { int arr [ ] = { 1 , 2 , 1 , 1 , 1 , 3 , 3 , 2 , 4 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << sumOfElements ( arr , n ) ; return 0 ; }