Count array elements whose count of divisors is a prime number | Function to count the array elements whose count of divisors is prime ; Stores the maximum element ; Find the maximum element ; Store if i - th element is prime ( 0 ) or non - prime ( 1 ) ; Base Case ; If i is a prime number ; Mark all multiples of i as non - prime ; Stores the count of divisors ; Base Case ; Iterate to count factors ; Stores the count of array elements whose count of divisors is a prime number ; Traverse the array arr [ ] ; If count of divisors is prime ; Return the resultant count ; Driver Code
def primeDivisors ( arr , N ) : NEW_LINE INDENT K = arr [ 0 ] NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT K = max ( K , arr [ i ] ) NEW_LINE DEDENT prime = [ 0 ] * ( K + 1 ) NEW_LINE prime [ 0 ] = 1 NEW_LINE prime [ 1 ] = 1 NEW_LINE for i in range ( 2 , K + 1 ) : NEW_LINE INDENT if ( not prime [ i ] ) : NEW_LINE INDENT for j in range ( 2 * i , K + 1 , i ) : NEW_LINE INDENT prime [ j ] = 1 NEW_LINE DEDENT DEDENT DEDENT factor = [ 0 ] * ( K + 1 ) NEW_LINE factor [ 0 ] = 0 NEW_LINE factor [ 1 ] = 1 NEW_LINE for i in range ( 2 , K + 1 ) : NEW_LINE INDENT factor [ i ] += 1 NEW_LINE for j in range ( i , K + 1 , i ) : NEW_LINE INDENT factor [ j ] += 1 NEW_LINE DEDENT DEDENT count = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT if ( prime [ factor [ arr [ i ] ] ] == 0 ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT arr = [ 10 , 13 , 17 , 25 ] NEW_LINE N = len ( arr ) NEW_LINE print ( primeDivisors ( arr , N ) ) NEW_LINE DEDENT