If prime is a factor of n then increment count
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 ) ; }