Nth HCF of two number

Question

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

for eg 16 , 8

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

I solved like this

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

But I want to know better approach

Thanks

this question is not really a programming question, it's a math question, is there any other mathematical solution then the one you sufficed? if not there is not much optimization you can do in programing — MoonBun, May 21 '15 at 09:12
why is HCF(16,8) 2 and not 8? On Wikipedia it sais that hcf=gcd — Luka Rahne, May 21 '15 at 09:17
There is a more trivial approach which is to test for each number m <= min (A,B) whether it divides A and B and to stop after the n-th one. This will be more efficient when n is small and A, B are very large. — vib, May 21 '15 at 09:22
@LukaRahne it is kind of unclear but HCF is the highest common factor, while 2nd HCF is second highest common factor mean the next highest after the first. Like max[1, 2, 4, 3] is 4 but 2nd max is 3.. — MoonBun, May 21 '15 at 09:27

score 3 · Answer 1 · edited May 23 '17 at 11:45

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.

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.

score 1 · Answer 2 · answered May 21 '15 at 10:57

You can derive your list of common factors from the prime factors of the hcf of the two numbers.

Here's a demo using code I had lying around. I use an implementation of the Extended Euclidean algorithm for the GCD just because I had one available. It's not necessarily the fastest solution.

/**
 * Prime factors of the number - not the most efficient but it works.
 *
 * @param n - The number to factorise.
 * @return - List of all prime factors of n.
 */
public static List<Long> primeFactors(long n) {
    return primeFactors(n, false);
}

/**
 * Prime factors of the number - not the most efficient but it works.
 *
 * @param n - The number to factorise.
 * @param unique - Want only unique factors.
 * @return - List of all prime factors of n.
 */
public static List<Long> primeFactors(long n, boolean unique) {
    Collection<Long> factors;
    if (unique) {
        factors = new HashSet<>();
    } else {
        factors = new ArrayList<>();
    }
    for (long i = 2; i <= n / i; i++) {
        while (n % i == 0) {
            factors.add(i);
            n /= i;
        }
    }
    if (n > 1) {
        factors.add(n);
    }
    return new ArrayList<>(factors);
}

/**
 * Extended Euclidean algorithm to find the GCD of a and b.
 *
 * We assume here that a and b are non-negative (and not both zero).
 *
 * This function also will return numbers j and k such that d = j*a + k*b where d is the GCD of a and b.
 */
public static int[] extendedEuclid(int a, int b) {
    int[] ans = new int[3];
    int q;
    // If b = 0, then we're done...
    if (b == 0) {
        // All over.
        ans[0] = a;
        ans[1] = 1;
        ans[2] = 0;
    } else {
        // Otherwise, make a recursive function call
        q = a / b;
        ans = extendedEuclid(b, a % b);
        int temp = ans[1] - ans[2] * q;
        ans[1] = ans[2];
        ans[2] = temp;
    }

    return ans;
}

/**
 * Common factors of the GCD of the two numbers.
 *
 * @param a - First number.
 * @param b - Second number.
 * @return - List of common factors.
 */
public static List<Long> cfs(int a, int b) {
    return primeFactors(extendedEuclid(a, b)[0]);
}

private static void test(int a, int b) {
    // Get the GCD.
    int[] ee = extendedEuclid(a, b);
    System.out.println("eEu(" + a + "," + b + ") = " + Arrays.toString(ee));
    // Get common factors.
    List<Long> cfs = cfs(a, b);
    System.out.println("cfs(" + a + "," + b + ") = " + cfs);
    // Build your list of what you call HCFs.
    List<Long> hcfs = new ArrayList<>();
    // Start at the GCD.
    long hcf = ee[0];
    for (Long l : cfs) {
        // Record that factor.
        hcfs.add(hcf);
        // Remove this prime factor from it.
        hcf /= l;
        // Obviously you could stop when you have your nth one.
    }
    // Also add `1`
    hcfs.add(1l);
    System.out.println("hcfs(" + a + "," + b + ") = " + hcfs);
}

public void test() {
    test(16, 8);
    test(144, 72);
}

This prints:

eEu(16,8) = [8, 0, 1]
cfs(16,8) = [2, 2, 2]
hcfs(16,8) = [8, 4, 2, 1]
eEu(144,72) = [72, 0, 1]
cfs(144,72) = [2, 2, 2, 3, 3]
hcfs(144,72) = [72, 36, 18, 9, 3, 1]

score 0 · Answer 3 · answered May 21 '15 at 10:18

0

Like what Bhoot said but even better: find all the factors up to sqrt(x) in an increasing order, like Bhoot factors_left.

Now for nth HCF you just get X / factors_left[n].

answered May 21 '15 at 10:18

MoonBun

4,322
3
37
69

Nth HCF of two number

3 Answers3

Linked