Count of natural numbers in range [ L , R ] which are relatively prime with N | Javascript code to count of natural numbers in range [ L , R ] which are relatively prime with N ; Container of all the primes up to sqrt ( n ) ; Function to calculate prime factors of n ; Run the sieve of Eratosthenes ; 0 ( false ) means prime , 1 ( true ) means not prime ; No even number is prime except for 2 ; All the multiples of each each prime numbers are non - prime ; Get all the primes in prime vector ; Count the number of numbers up to m which are divisible by given prime numbers ; Run from i = 000. . 0 to i = 111. . 1 or check all possible subsets of the array ; If the number of set bits is odd , then add to the number of multiples ; Function calculates all number not greater than ' m ' which are relatively prime with n . ; If square of the prime number is greater than ' n ' , it can ' t ▁ ▁ be ▁ a ▁ factor ▁ of ▁ ' n ' ; If prime is a factor of n then increment count ; Driver code
let maxN = 100000000 ; let prime = [ ] ; function sieve ( n ) { let check = new Array ( 1000007 ) ; for ( let i = 0 ; i < 1000007 ; i ++ ) check [ i ] = false ; let i , j ; check [ 0 ] = false ; check [ 1 ] = true ; check [ 2 ] = false ; for ( i = 4 ; i <= n ; i += 2 ) check [ i ] = true ; for ( i = 3 ; i * i <= n ; i += 2 ) if ( ! check [ i ] ) { for ( j = i * i ; j <= n ; j += 2 * i ) check [ j ] = true ; } prime . push ( 2 ) ; for ( i = 3 ; i <= n ; i += 2 ) if ( ! check [ i ] ) prime . push ( i ) ; return ; } function countSetBits ( n ) { let count = 0 ; while ( n > 0 ) { count += n & 1 ; n >>= 1 ; } return count ; } function count ( a , n , m ) { let parity = new Array ( 3 ) ; for ( let i = 0 ; i < 3 ; i ++ ) parity [ i ] = 0 ; for ( let i = 1 ; i < ( 1 << n ) ; i ++ ) { let mult = 1 ; for ( let j = 0 ; j < n ; j ++ ) if ( ( i & ( 1 << j ) ) != 0 ) mult *= a [ j ] ; parity [ countSetBits ( i ) & 1 ] += ( m / mult ) ; } return parity [ 1 ] - parity [ 0 ] ; } function countRelPrime ( n , m ) { let a = new Array ( 20 ) ; let i = 0 , j = 0 ; let pz = prime . length ; while ( n != 1 && i < pz ) { if ( prime [ i ] * prime [ i ] > n ) break ; if ( n % prime [ i ] == 0 ) { a [ j ] = prime [ i ] ; j ++ ; } while ( n % prime [ i ] == 0 ) n = Math . floor ( n / prime [ i ] ) ; i ++ ; } if ( n != 1 ) { a [ j ] = n ; j ++ ; } return m - count ( a , j , m ) ; } function countRelPrimeInRange ( n , l , r ) { sieve ( Math . floor ( Math . sqrt ( maxN ) ) ) ; let result = countRelPrime ( n , r ) - countRelPrime ( n , l - 1 ) ; document . write ( result ) ; } let N = 7 , L = 3 , R = 9 ; countRelPrimeInRange ( N , L , R ) ;