Count numbers having GCD with N equal to the number itself | Function to count numbers whose GCD with N is the number itself ; Stores the count of factors of N ; Iterate over the range [ 1 , sqrt ( N ) ] ; If i is divisible by i ; Increment count ; Avoid counting the same factor twice ; Return the resultant count ; Driver Code
def countNumbers ( N ) : NEW_LINE INDENT count = 0 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT if i * i > N : NEW_LINE INDENT break NEW_LINE DEDENT if ( N % i == 0 ) : NEW_LINE INDENT count += 1 NEW_LINE if ( N // i != i ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 10 NEW_LINE print ( countNumbers ( N ) ) NEW_LINE DEDENT