Fast HCF C# Code | Efficient GCD Algorithm Tutorial

Fast C# Code to Find HCF (GCD)

This tutorial demonstrates an efficient C# 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 C# handles numerical sorting and divisor checks.
The H.C.F. code in C# from the previous Finding HCF and GCD in C# lesson could get a bit slow if 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 C# 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 C# code for the main class from the previous lesson if you have been following.

So! C# Fun Practice Exercise - Fast Find HCF

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

C# Code for Fast HCF class.

using System;
using System.Collections.Generic;

namespace Arithmetic
{
    class FastHCF
    {
        private int[] set_of_numbers;
        private int[] arg_copy; // Java passes arrays by reference; make a copy.
        private List<int> common_factors = new List<int>(); // factors common to our set_of_numbers
        private List<int> min_prime_factors = new List<int>();

        private int index; // index into array common_factors
        private bool all_round_factor; // intiable to keep state
        private int calc_result;

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

            // STEP 1:
            group.Sort();
            //iterate through and retrieve members
            foreach (int number in group)
            {
                set_of_numbers[index] = number;
                arg_copy[index] = number;
                index++;
            }

            all_round_factor = false;
            calc_result = 1;
        }

        // STEP 2:
        /*
         * Compiles only the factors of the smallest member of 'group_of_numbers'
         */
        private int onlyPrimeFactors(int in_question)
        {
            int temp_limit;
            temp_limit = (int)Math.Ceiling(Math.Sqrt(in_question));

            while (index <= temp_limit)
            {
                if ((in_question % index) == 0)
                {
                    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.Count)
            {
                all_round_factor = true;
                // STEP 3:
                for (int j = 0; j < arg_copy.Length; j++)
                {
                    if (!(all_round_factor == true
                            && (arg_copy[j] % min_prime_factors[index]) == 0))
                    {
                        all_round_factor = false;
                    }
                }

                // STEP 4:
                if (all_round_factor == true)
                {
                    for (int j = 0; j < arg_copy.Length; j++)
                    {
                        arg_copy[j] /= min_prime_factors[index];
                    }
                    common_factors.Add(min_prime_factors[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
            foreach (int factor in common_factors)
            {
                calc_result *= factor;
            }

            return calc_result;
        }
    }
}

C# Code for Fast HCF - Main Class.

using System;
using System.Collections.Generic;

namespace Arithmetic
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Welcome to our demonstration sequels");
            Console.WriteLine("Hope you enjoy (and follow) the lessons.");
            Console.WriteLine("\r\n");

            /*
            * Find HCF.
             */
            List<int> set = new List<int>();
            set.Add(30);
            set.Add(48);
            set.Add(54);

            FastHCF hcf = new FastHCF(set);

            Console.WriteLine("The H.C.F. of " + String.Join(", ", set) + " is " + hcf.getHCF());

        }
    }
}

I have a better version / See other versions.