Largest Coprime Divisor

You are given two positive numbers A and B. You need to find the maximum valued integer X such that:

For example,

A = 30
B = 12
We return
X = 5

思路：

假如A和B coprime，那么返回A就可以了，否则我们找到A和B的gcd，然后对A / gcd, B 测试。直到A和B coprime。

Solution:

Time: O(logA * logA)

public class Solution {
    public int cpFact(int A, int B) {
        int gcd = gcd(A, B);
        if (gcd == 1) {
            return A;
        } else {
            return cpFact(A / gcd, B);
        }
    }
    
    private int gcd(int A, int B) {
        if (B == 0) return A;
        return gcd(B, A % B);
    }
}