两个数的第N个HCF

问题描述

我遇到了一个编码测验，假设两个A和B没有找到两个N中的第n个HCF

I came across a coding quiz, given two no A and B find the nth HCF of the two no

例如16，8

HCF 8、4、2、1 所以3rd HCF是2

HCF 8, 4, 2, 1 so 3rd HCF is 2

我这样解决

   1. X =  GCD(A,B)
   2. Find all factor of X
   3. Sort the factor in order

但是我想知道更好的方法

But I want to know better approach

谢谢

推荐答案

我认为您在上面的描述中提到的方法是最佳的，除了最后一步，您基本上不需要对因素进行排序-您可以简单地生成他们以递增的顺序.

I think that the approach you have mentioned in description above is optimal except for the last step where you essentially do not need to sort the factors - you can simply generate them in increasing order.

您可以阅读关于Euclid算法复杂度的有趣讨论第一步的复杂性.计算完GCD后，发现所有因素都会花费O(sqrt(gcd))时间.您可以按递增顺序生成它们，如下所示:

You can read this interesting discussion on complexity of Euclid Algorithm which is the time complexity for your first step.Once GCD has been computed, finding all its factors will take O(sqrt(gcd)) time. You can generate them in increasing order as follows:

public ArrayList<Integer> factorize(int x) {
    ArrayList<Integer> factors_left = new ArrayList<>();
    ArrayList<Integer> factors_right = new ArrayList<>();
    for(int i=1; i<=(int)sqrt(x)+1; i++) {
        if(x%i==0) {
            factors_left.add(i);
            factors_right.add(x/i);
        }
    }
    ArrayList<Integer> allfactors = new ArrayList<>();
    for(int f: factors_left) {
        allfactors.add(f);
    }
    for(int i=factors_right.size()-1; i>=0; i--) {
        allfactors.add(factors_right.get(i));
    }
    return allfactors;
}

您现在可以简单地遍历此列表以找到所需的因子.

You can now simply traverse this list to find the desired factor.

这篇关于两个数的第N个HCF的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！