Count of elements not divisible by any other elements of Array | C ++ program for the above approach ; Function to count the number of elements of array which are not divisible by any other element of same array ; Length for boolean array ; Hash map for storing the element and it 's frequency ; Update the maximum element ; Boolean array of size of the max element + 1 ; Marking the multiples as false ; To store the final count ; Traverse boolean array ; Check if i is not divisible by any other array elements and appears in the array only once ; Return the final Count ; Driver Code ; Given array ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countEle ( int a [ ] , int n ) { int len = 0 ; unordered_map < int , int > hmap ; for ( int i = 0 ; i < n ; i ++ ) { len = max ( len , a [ i ] ) ; hmap [ a [ i ] ] ++ ; } bool v [ len + 1 ] ; for ( int i = 0 ; i <= len ; i ++ ) { v [ i ] = true ; } for ( int i = 0 ; i < n ; i ++ ) { if ( v [ a [ i ] ] == false ) continue ; for ( int j = 2 * a [ i ] ; j <= len ; j += a [ i ] ) { v [ j ] = false ; } } int count = 0 ; for ( int i = 1 ; i <= len ; i ++ ) { if ( v [ i ] == true && hmap . count ( i ) == 1 && hmap [ i ] == 1 ) { count += 1 ; } } return count ; } int main ( ) { int arr [ ] = { 86 , 45 , 18 , 4 , 8 , 28 , 19 , 33 , 2 } ; int n = sizeof ( arr ) / sizeof ( int ) ; cout << countEle ( arr , n ) ; return 0 ; }