public class EuclidsAlgorithm { public static int gcd(int p, int q) { if (p == 0) return p; int r = p % q; return gcd(q, r); } }