Count of numbers up to N having at least one prime factor common with N | Function to count all the numbers in the range [ 1 , N ] having common factor with N other than 1 ; Stores the count of numbers having more than 1 factor with N ; Iterate over the range [ 1 , N ] ; If gcd is not 1 then increment the count ; Prvar the resultant count ; Driver Code
function countNumbers ( N ) { var count = 0 ; for ( var i = 1 ; i <= N ; i ++ ) { if ( __gcd ( i , N ) != 1 ) count ++ ; } document . write ( count ) ; } function __gcd ( a , b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } var N = 5 ; countNumbers ( N ) ;