Fast HCF Java Code | Efficient GCD Algorithm Tutorial

Fast Java Code to Find HCF (GCD)

This tutorial demonstrates an efficient Java method to calculate the Highest Common Factor (HCF), also known as the Greatest Common Divisor (GCD). Using prime factorization and loop optimization, students can learn how Java handles numerical sorting and divisor checks.
The H.C.F. code in Java from the previous Finding HCF and GCD in Java lesson could get a bit slowif we run into a prime number and this prime number becomes the loop range.

Let's see how we can fix this and make a fast Java algorithm to find HCF:

Step 1:

Do a numerical sort on the resulting set so its first member is the smallest in the set.

Step 2:

Find the factors of the first number in the set.

Step 3:

Iteratively check through the set of numbers with the factors from Step 2 to make sure it is common to all.

Step 4:

For each common factor, divide every member of the number set by the common factor.

Note: You can comment out the Java code for the main class from the previous lesson if you have been following.

So! Java Fun Practice Exercise - Fast Find HCF

As a fun practice exercise, feel free to try out your own numbers, and see how the fast Java code finds the HCF of those numbers.

Java Code for Fast HCF class.

package arithmetic;

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

public class FastHCF {

    private final int[] set_of_numbers;
    private final int[] arg_copy; // Java passes arrays by reference; make a copy.
    private final List<Integer> common_factors = new ArrayList<>(); // factors common to our set_of_numbers
    private final List<Integer> min_prime_factors = new ArrayList<>();

    private int index; // index into array common_factors
    private boolean all_round_factor; // intiable to keep state
    private int calc_result;
    private Comparator c;

    public FastHCF(List<Integer> group) {
        set_of_numbers = new int[group.size()];
        arg_copy = new int[group.size()];
        index = 0;

        group.sort(c);
        //iterate through and retrieve members
        for (int number : group) {
            set_of_numbers[index] = number;
            arg_copy[index] = number;
            index++;
        }

        all_round_factor = false;
        calc_result = 1;
    }

    private int onlyPrimeFactors(int in_question) {
        int temp_limit;
        temp_limit = (int) Math.ceil(Math.sqrt(in_question));

        while (index <= temp_limit) {
            if ((in_question % index) == 0) { // avoid an infinite loop with the i != 1 check.
                min_prime_factors.add(index);
                return onlyPrimeFactors(in_question / index);
            }
            index++;
        }
        min_prime_factors.add(in_question);

        return 0;
    }

    /**
     * This function searches for mutual factors using an already computed
     * list of factors(for the smallest member of 'set_of_numbers').
     * @return - Nil
     */
    private int findHCFFactors() {
        while (index < min_prime_factors.size()) {

            all_round_factor = true;
            for (int j = 0; j < arg_copy.length; j++) {
                if (!(all_round_factor == true &&
                (arg_copy[j] % min_prime_factors.get(index)) == 0))
                {
                    all_round_factor = false;
                }
            }
            if (all_round_factor == true) {
                for (int j = 0; j < arg_copy.length; j++) {
                    arg_copy[j] /= min_prime_factors.get(index);
                }
                common_factors.add(min_prime_factors.get(index));
            }
            index++;
        }

        return 0;
    }

    /**
     * Just calls out and collects the prepared factors.
     * @return - String value
     */
    public int getHCF() {
        index = 2;
        onlyPrimeFactors(set_of_numbers[0]);

        index = 0;
        findHCFFactors();

        //iterate through and retrieve members
        common_factors.stream().forEach((factor) -> {
            calc_result *= factor;
        });

        return calc_result;
    }
}

Java Code for Fast HCF - Main Class.

package arithmetic;

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

public class Arithmetic {

    public static void main(String[] args) {
        System.out.println("Welcome to our demonstration sequels");
        System.out.println("Hope you enjoy (and follow) the lessons.");
        System.out.println("");

        List<Integer> set;
        set = new ArrayList<>();
        set.add(30);
        set.add(48);
        set.add(54);

        String render_result = "The HCF of ";
        for (int number : set) {
            render_result += number + "; ";
        }
        render_result += "is:  ";

        //Use fast copy
        FastHCF h_c_f;
        h_c_f = new FastHCF(set);
        System.out.println(render_result + h_c_f.getHCF());
    }

}

I have a better version / See other versions.