def _r_count_num_m(n, factors_d, i):
    """Count of numbers coprime to d less than end; sum( gcd(m, d) == 1 for m in range(n, n+i) )

    Uses inclusion exclusion on prime factorization of d
    """

    if n == 0:
        return 0

    if i < 0:
        return n

    return _r_count_num_m(n, factors_d, i-1) - _r_count_num_m(n // factors_d[i], factors_d, i-1)