Count of pairs upto N such whose LCM is not equal to their product for Q queries | Python 3 program to find the count of pairs from 1 to N such that their LCM is not equal to their product ; To store Euler 's Totient Function ; To store prefix sum table ; Compute Totients of all numbers smaller than or equal to N ; Make phi [ 1 ] = 0 since 1 cannot form any pair ; Initialise all remaining phi [ ] with i ; Compute remaining phi ; If phi [ p ] is not computed already , then number p is prime ; phi of prime number is p - 1 ; Update phi of all multiples of p ; Add the contribution of p to its multiple i by multiplying it with ( 1 - 1 / p ) ; Function to store prefix sum table ; Prefix Sum of all Euler 's Totient Values ; Total number of pairs that can be formed ; Driver Code ; Function call to compute all phi ; Function call to store all prefix sum
N = 100005 NEW_LINE phi = [ 0 for i in range ( N ) ] NEW_LINE pref = [ 0 for i in range ( N ) ] NEW_LINE def precompute ( ) : NEW_LINE INDENT phi [ 1 ] = 0 NEW_LINE for i in range ( 2 , N , 1 ) : 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 prefix ( ) : NEW_LINE INDENT for i in range ( 1 , N , 1 ) : NEW_LINE INDENT pref [ i ] = pref [ i - 1 ] + phi [ i ] NEW_LINE DEDENT DEDENT def find_pairs ( n ) : NEW_LINE INDENT total = ( n * ( n - 1 ) ) // 2 NEW_LINE ans = total - pref [ n ] NEW_LINE print ( " Number ▁ of ▁ pairs ▁ from ▁ 1 ▁ to " , n , " are " , ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT precompute ( ) NEW_LINE prefix ( ) NEW_LINE q = [ 5 , 7 ] NEW_LINE n = len ( q ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT find_pairs ( q [ i ] ) NEW_LINE DEDENT DEDENT