import java.util.ArrayList;
import java.util.List;

public class Solution {

    // 返回質因數分解
    List<Integer> getPrimeFactors(int n) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 2; i <= n; i++) {
            // 注意while的終止條件是n!=i
            while (n != i) {
                if (n % i == 0) {
                    list.add(i);
                    n = n / i;
                } else
                    break;
            }
        }
        list.add(n);
        return list;

    }

    public static void main(String[] args) {
        System.out.println(new Solution().getPrimeFactors(120));

    }
}

public class Solution {
    /**
     * 輾轉相除法 缺點：對于大整數求模是瓶頸
     */
    public int gcd1(int x, int y) {
        return y == 0 ? x : gcd1(y, x % y);
    }

    /**
     * 更相減損術 缺點：某些case下遞歸次數太多，不如gcd(100000,1)的情況。
     */
    public int gcd2(int x, int y) {
        if (x < y)
            return gcd2(y, x);
        if (y == 0)
            return x;
        else
            return gcd2(x - y, y);

    }

    /**
     * 編程之美上的方法，避免了以上兩種方法的劣勢， 復雜度O(log(max(x,y)));
     */
    public int gcd(int x, int y) {
        if (x < y)
            return gcd(y, x);
        if (y == 0)
            return x;
        else {
            if (isEven(x)) {
                if (isEven(y)) {
                    return gcd(x >> 1, y >> 1) << 1;
                } else {
                    return gcd(x >> 1, y);
                }

            } else {
                if (isEven(y)) {
                    return gcd(x, y >> 1);
                } else {
                    return gcd(y, x - y);
                }

            }

        }

    }

    private boolean isEven(int x) {
        return (x & 1) == 0;
    }

    public static void main(String[] args) {
        int a = 420000, b = 3050;
        System.out.println(new Solution().gcd1(a, b));
        System.out.println(new Solution().gcd2(a, b));
        System.out.println(new Solution().gcd(a, b));

    }
}