GCD and Coprime Numbers Problem

Problem: A number-theory problem built around GCD and coprimality - e.g., given two numbers, determine if they are coprime (GCD == 1), or find how many numbers in a range are coprime to a given number.

Constraints: Inputs can be large enough that brute-force factorization is too slow; expect time limits favoring O(log(min(a,b))) GCD computation.

Example: Input: a=8, b=15 GCD(8,15) = 1 -> coprime.

Approach: Use the Euclidean algorithm (gcd(a,b) = gcd(b, a % b), base case gcd(a,0)=a) for O(log(min(a,b))) GCD computation. For counting coprimes in a range, combine GCD checks with sieve-based prime factorization or Euler's Totient function depending on problem constraints.