Count of elements not divisible by any other elements of Array | 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
def countEle ( a , n ) : NEW_LINE INDENT len = 0 NEW_LINE hmap = { } NEW_LINE for i in range ( n ) : NEW_LINE INDENT len = max ( len , a [ i ] ) NEW_LINE hmap [ a [ i ] ] = hmap . get ( a [ i ] , 0 ) + 1 NEW_LINE DEDENT v = [ True for i in range ( len + 1 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( v [ a [ i ] ] == False ) : NEW_LINE INDENT continue NEW_LINE DEDENT for j in range ( 2 * a [ i ] , len + 1 , a [ i ] ) : NEW_LINE INDENT v [ j ] = False NEW_LINE DEDENT DEDENT count = 0 NEW_LINE for i in range ( 1 , len + 1 ) : NEW_LINE INDENT if ( v [ i ] == True and ( i in hmap ) and hmap [ i ] == 1 ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 86 , 45 , 18 , 4 , 8 , 28 , 19 , 33 , 2 ] NEW_LINE n = len ( arr ) NEW_LINE print ( countEle ( arr , n ) ) NEW_LINE DEDENT