Count of numbers up to N having at least one prime factor common with N | Function to calculate the value of Euler 's totient function ; Initialize result with N ; Find all prime factors of N and subtract their multiples ; Check if p is a prime factor ; If found to be true , then update N and result ; If N has a prime factor greater than sqrt ( N ) , then there can be at - most one such prime factor ; Function to count all the numbers in the range [ 1 , N ] having common factor with N other than 1 ; Stores the resultant count ; Prlet the count ; Driver Code
function phi ( N ) { let result = N ; for ( let p = 2 ; p * p <= N ; ++ p ) { if ( N % p == 0 ) { while ( N % p == 0 ) N /= p ; result -= result / p ; } } if ( N > 1 ) result -= result / N ; return result ; } function countNumbers ( N ) { let count = N - phi ( N ) ; document . write ( count ) ; } let N = 5 ; countNumbers ( N ) ;