Count of pairs upto N such whose LCM is not equal to their product for Q queries | javascript 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 ; Function call to compute all phi ; Function call to store all prefix sum
var N = 100005 ; var phi = Array ( N ) . fill ( 0 ) ; var pref = Array ( N ) . fill ( 0 ) ; function precompute ( ) { phi [ 1 ] = 0 ; for ( i = 2 ; i < N ; i ++ ) phi [ i ] = i ; for ( p = 2 ; p < N ; p ++ ) { if ( phi [ p ] == p ) { phi [ p ] = p - 1 ; for ( i = 2 * p ; i < N ; i += p ) { phi [ i ] = ( phi [ i ] / p ) * ( p - 1 ) ; } } } } function prefix ( ) { for ( i = 1 ; i < N ; i ++ ) pref [ i ] = pref [ i - 1 ] + phi [ i ] ; } function find_pairs ( n ) { var total = ( n * ( n - 1 ) ) / 2 ; var ans = total - pref [ n ] ; document . write ( " " + n + " " + ans + " " ) ; } precompute ( ) ; prefix ( ) ; var q = [ 5 , 7 ] ; var n = q . length ; for ( i = 0 ; i < n ; i ++ ) { find_pairs ( q [ i ] ) ; }