I am trying to solve Coprime Integers. I believe the central idea to the problem involves the ETF, as I can solve the number of integers between a <= x <= b such that gcd(x, n) = 1, and loop this (or possibly leverage Euler Phi Function) for all c <= n <= d. If anyone has a general explanation of the solution, this would also be helpful.

Nevertheless, ETF is "the number of integers [1...n] that are coprime with n. I need "the number of integers [1...c] that are coprime with n.

For example, if n=40=2^3*5 and c=12, then the following 5 pairs are valid: (1,40), (3,40), (7,40), (9,40), (11,40). I think the way this should be generated is this: total number of integers — number of integers not coprime + the number of double counts= 12 — floor(12/2) — floor(12/5) + floor(12/10) = 5. However, this is too inefficient as inclusion-exclusion may take a long time.

I know that the ETF is multiplicative and that phi(P1^x * P2^y) = phi(P1^x) * phi(P2^y). However, this calculates the first ETF definition given above, not the second type which is what I need. How can I transform this to work for my need? And what is the reason behind it? My math is not super strong, so details would be helpful!