Count of natural numbers in range [ L , R ] which are relatively prime with N | Java 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
import java . util . * ; class GFG { static int maxN = 100000000 ; static Vector < Integer > prime = new Vector < Integer > ( ) ; static void sieve ( int n ) { boolean [ ] check = new boolean [ 1000007 ] ; for ( int i = 0 ; i < 1000007 ; i ++ ) check [ i ] = false ; int 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 . add ( 2 ) ; for ( i = 3 ; i <= n ; i += 2 ) if ( ! check [ i ] ) prime . add ( i ) ; return ; } static int countSetBits ( int n ) { int count = 0 ; while ( n > 0 ) { count += n & 1 ; n >>= 1 ; } return count ; } static int count ( int a [ ] , int n , int m ) { int [ ] parity = new int [ 3 ] ; for ( int i = 0 ; i < 3 ; i ++ ) parity [ i ] = 0 ; for ( int i = 1 ; i < ( 1 << n ) ; i ++ ) { int mult = 1 ; for ( int j = 0 ; j < n ; j ++ ) if ( ( i & ( 1 << j ) ) != 0 ) mult *= a [ j ] ; parity [ countSetBits ( i ) & 1 ] += ( m / mult ) ; } return parity [ 1 ] - parity [ 0 ] ; } static int countRelPrime ( int n , int m ) { int [ ] a = new int [ 20 ] ; int i = 0 , j = 0 ; int pz = prime . size ( ) ; while ( n != 1 && i < pz ) { if ( ( int ) prime . get ( i ) * ( int ) prime . get ( i ) > n ) break ; if ( n % prime . get ( i ) == 0 ) { a [ j ] = ( int ) prime . get ( i ) ; j ++ ; } while ( n % prime . get ( i ) == 0 ) n /= prime . get ( i ) ; i ++ ; } if ( n != 1 ) { a [ j ] = n ; j ++ ; } return m - count ( a , j , m ) ; } static void countRelPrimeInRange ( int n , int l , int r ) { sieve ( ( int ) Math . sqrt ( maxN ) ) ; int result = countRelPrime ( n , r ) - countRelPrime ( n , l - 1 ) ; System . out . println ( result ) ; } public static void main ( String [ ] args ) { int N = 7 , L = 3 , R = 9 ; countRelPrimeInRange ( N , L , R ) ; } }