Queries to count the number of unordered co | Javascript 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 ; function call
let N = 100005 ; let phi = new Array ( N ) ; let S = new Array ( N ) ; for ( let i = 0 ; i < N ; i ++ ) { phi [ i ] = 0 ; S [ i ] = 0 ; } function computeTotient ( ) { for ( let i = 1 ; i < N ; i ++ ) phi [ i ] = i ; for ( let p = 2 ; p < N ; p ++ ) { if ( phi [ p ] == p ) { phi [ p ] = p - 1 ; for ( let i = 2 * p ; i < N ; i += p ) { phi [ i ] = ( phi [ i ] / p ) * ( p - 1 ) ; } } } } function CoPrimes ( ) { computeTotient ( ) ; for ( let i = 1 ; i < N ; i ++ ) S [ i ] = S [ i - 1 ] + phi [ i ] ; } CoPrimes ( ) ; let q = [ 3 , 4 ] ; let n = q . length ; for ( let i = 0 ; i < n ; i ++ ) document . write ( " " + " " + q [ i ] + " " + S [ q [ i ] ] + " " ) ;