Count of integers up to N which are non divisors and non coprime with N | Function to return the count of letegers less than N satisfying given conditions ; Stores Euler counts ; Store Divisor counts ; Based on Sieve of Eratosthenes ; Update phi values of all multiples of i ; Update count of divisors ; Return the final count ; Driver code
function count ( n ) { let phi = [ ] ; let divs = [ ] ; for ( let i = 1 ; i <= n ; i ++ ) { phi [ i ] = 0 ; divs [ i ] = 0 ; } for ( let i = 1 ; i <= n ; i ++ ) { phi [ i ] += i ; for ( let j = i * 2 ; j <= n ; j += i ) phi [ j ] -= phi [ i ] ; for ( let j = i ; j <= n ; j += i ) divs [ j ] ++ ; } return ( n - phi [ n ] - divs [ n ] + 1 ) ; } let N = 42 ; document . write ( count ( N ) ) ;