Count of integers up to N which are non divisors and non coprime with N | Function to return the count of integers less than N satisfying given conditions ; Stores Euler counts ; Store Divisor counts ; Based on Sieve of Eratosthenes ; Update phi values of all multiples of i ; Update count of divisors ; Return the final count ; Driver code
def count ( n ) : NEW_LINE INDENT phi = [ 0 ] * ( n + 1 ) NEW_LINE divs = [ 0 ] * ( n + 1 ) NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT phi [ i ] += i NEW_LINE for j in range ( i * 2 , n + 1 , i ) : NEW_LINE INDENT phi [ j ] -= phi [ i ] ; NEW_LINE DEDENT for j in range ( i , n + 1 , i ) : NEW_LINE INDENT divs [ j ] += 1 NEW_LINE DEDENT DEDENT return ( n - phi [ n ] - divs [ n ] + 1 ) ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 42 NEW_LINE print ( count ( N ) ) NEW_LINE DEDENT