if prime is a factor of n then increment count
if ( n % prime [ i ] == 0 ) a [ j ] = ( long long ) prime [ i ] , j ++ ; while ( n % prime [ i ] == 0 ) n /= prime [ i ] ; i ++ ; } if ( n != 1 ) a [ j ] = n , j ++ ; return m - count ( a , j , m ) ; } void countRelPrimeInRange ( long long n , long long l , long long r ) { sieve ( sqrt ( maxN ) ) ; long long result = countRelPrime ( n , r ) - countRelPrime ( n , l - 1 ) ; cout << result << " STRNEWLINE " ; }