Queries to count the number of unordered co | Python3 program to find number of unordered coprime pairs of integers from 1 to N ; to store euler 's totient function ; to store required answer ; Computes and prints totient of all numbers smaller than or equal to N . ; Initialise the phi [ ] with 1 ; Compute other Phi values ; If phi [ p ] is not computed already , then number p is prime ; Phi of a prime number p is always equal to p - 1. ; Update phi values of all multiples of p ; Add contribution of p to its multiple i by multiplying with ( 1 - 1 / p ) ; function to compute number coprime pairs ; function call to compute euler totient function ; prefix sum of all euler totient function values ; Driver code ; function call
N = 100005 NEW_LINE phi = [ 0 ] * N NEW_LINE S = [ 0 ] * N NEW_LINE def computeTotient ( ) : NEW_LINE INDENT for i in range ( 1 , N ) : NEW_LINE INDENT phi [ i ] = i NEW_LINE DEDENT for p in range ( 2 , N ) : NEW_LINE INDENT if ( phi [ p ] == p ) : NEW_LINE INDENT phi [ p ] = p - 1 NEW_LINE for i in range ( 2 * p , N , p ) : NEW_LINE INDENT phi [ i ] = ( phi [ i ] // p ) * ( p - 1 ) NEW_LINE DEDENT DEDENT DEDENT DEDENT def CoPrimes ( ) : NEW_LINE INDENT computeTotient ( ) NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT S [ i ] = S [ i - 1 ] + phi [ i ] NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT CoPrimes ( ) NEW_LINE q = [ 3 , 4 ] NEW_LINE n = len ( q ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT print ( " Number of unordered coprime " ▁ + ▁ " pairs of integers from 1 to " , ▁ q [ i ] , ▁ " are   " , S [ q [ i ] ] ) NEW_LINE DEDENT DEDENT