Count of non co | JavaScript program for the above approach ; Auxiliary function to pre - compute the answer for each array ; Iterate over the range [ 1 , MAX ] ; Iterate over the range [ 1 , MAX ] ; If the number is prime ; Subtract the number of pairs which has i as one of their factors ; Iterate over the range [ 1 , MAX ] ; Function to count the number of non co - prime pairs for each query ; The i - th element stores the count of element that are co - prime with i ; Stores the resulting array ; Function Call ; Traverse the array arr [ ] ; Given Input ; Function Call
const MAX = 1005 ; function preCalculate ( phi , ans ) { phi [ 0 ] = 0 ; phi [ 1 ] = 1 ; for ( let i = 2 ; i <= MAX ; i ++ ) phi [ i ] = i ; for ( let i = 2 ; i <= MAX ; i ++ ) { if ( phi [ i ] == i ) { for ( let j = i ; j <= MAX ; j += i ) phi [ j ] -= Math . floor ( phi [ j ] / i ) ; } } for ( let i = 1 ; i <= MAX ; i ++ ) ans [ i ] = ans [ i - 1 ] + ( i - phi [ i ] ) ; } function countPairs ( arr , N ) { let phi = new Array ( 1e5 ) . fill ( 0 ) ; let ans = new Array ( 1e5 ) . fill ( 0 ) ; preCalculate ( phi , ans ) ; for ( let i = 0 ; i < N ; ++ i ) { document . write ( ans [ arr [ i ] ] + " " ) ; } } let arr = [ 5 , 10 , 20 ] ; let N = 3 ; countPairs ( arr , N ) ;