Count of numbers up to N having at least one prime factor common with N | Function to calculate the value of Euler 's totient function ; Initialize result with N ; Find all prime factors of N and subtract their multiples ; Check if p is a prime factor ; If found to be true , then update N and result ; If N has a prime factor greater than sqrt ( N ) , then there can be at - most one such prime factor ; Function to count all the numbers in the range [ 1 , N ] having common factor with N other than 1 ; Stores the resultant count ; Print the count ; Driver Code
def phi ( N ) : NEW_LINE INDENT result = N NEW_LINE for p in range ( 2 , int ( pow ( N , 1 / 2 ) ) + 1 ) : NEW_LINE INDENT if ( N % p == 0 ) : NEW_LINE INDENT while ( N % p == 0 ) : NEW_LINE INDENT N = N / p NEW_LINE DEDENT result -= result // p NEW_LINE DEDENT DEDENT if ( N > 1 ) : NEW_LINE INDENT result -= result // N NEW_LINE DEDENT return result NEW_LINE DEDENT def countNumbers ( N ) : NEW_LINE INDENT count = N - phi ( N ) NEW_LINE print ( count ) NEW_LINE DEDENT N = 5 NEW_LINE countNumbers ( N ) NEW_LINE