Count integers in a range which are divisible by their euler totient value | Function to return a ^ n ; Function to return count of integers that satisfy n % phi ( n ) = 0 ; Driver Code
def power ( a , n ) : NEW_LINE INDENT if n == 0 : NEW_LINE INDENT return 1 NEW_LINE DEDENT p = power ( a , n // 2 ) NEW_LINE p = p * p NEW_LINE if n & 1 : NEW_LINE INDENT p = p * a NEW_LINE DEDENT return p NEW_LINE DEDENT def countIntegers ( l , r ) : NEW_LINE INDENT ans , i = 0 , 1 NEW_LINE v = power ( 2 , i ) NEW_LINE while v <= r : NEW_LINE INDENT while v <= r : NEW_LINE INDENT if v >= l : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT v = v * 3 NEW_LINE DEDENT i += 1 NEW_LINE v = power ( 2 , i ) NEW_LINE DEDENT if l == 1 : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT l , r = 12 , 21 NEW_LINE print ( countIntegers ( l , r ) ) NEW_LINE DEDENT