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 - Header File.

#pragma once

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>

using namespace std;

class FastHCF {
public:
    FastHCF(vector<unsigned>);
    virtual ~FastHCF();
    unsigned getHCF(void);
private:
    int onlyPrimeFactors(unsigned);
    int findHCFFactors(void);

    int * set_of_numbers;
    int * arg_copy;
    size_t array_length;
    vector<unsigned> common_factors; // factors common to our set_of_numbers
    vector<unsigned> minimal_prime_factors;
    unsigned int index; // index into array common_factors
    bool all_round_factor; // variable to keep state
    unsigned int calc_result; // helps calculate HCF
};

C++ Code for Fast HCF - Class File.

#include "stdafx.h"
#include "FastHCF.h"

FastHCF::FastHCF(vector<unsigned> group) {
    common_factors = {};
    group.shrink_to_fit();
    sort(group.begin(), group.end());

    array_length = group.size();
    set_of_numbers = new int[array_length];
    arg_copy = new int[array_length];
    index = 0;

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

    index = 2;
    all_round_factor = false;
}

int FastHCF::onlyPrimeFactors(unsigned in_question) {
    int temp_limit;
    temp_limit = (int)ceil(sqrt(in_question));

    while (index <= temp_limit) {
        if (index != 1 && (in_question % index) == 0) { // avoid an infinite loop with the i != 1 check.
            minimal_prime_factors.push_back(index);
            return onlyPrimeFactors(in_question / index);
        }
        index++;
    }
    minimal_prime_factors.push_back(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
*/
int FastHCF::findHCFFactors() {
    while (index < minimal_prime_factors.size()) {

        all_round_factor = true;
        for (int j = 0; j < array_length; j++) {
            if (!(all_round_factor == true &&
                (arg_copy[j] % minimal_prime_factors[index]) == 0)) {
                all_round_factor = false;
            }
        }
        if (all_round_factor == true) {
            for (int j = 0; j < array_length; j++) {
                arg_copy[j] /= minimal_prime_factors[index];
            }
            common_factors.push_back(minimal_prime_factors[index]);
        }
        index++;
    }

    return 0;
}

/**
* Just calls out and collects the prepared factors.
*/
unsigned FastHCF::getHCF() {
    index = 2;
    onlyPrimeFactors(set_of_numbers[0]);
    minimal_prime_factors.shrink_to_fit();

    index = 0;
    findHCFFactors();
    common_factors.shrink_to_fit();

    //iterate through and retrieve members
    calc_result = 1;
    for (unsigned factor : common_factors) {
        calc_result *= factor;
    };

    return calc_result;
}

FastHCF::~FastHCF() {
    delete[] set_of_numbers;
    delete[] arg_copy;
}

C++ Code for Fast HCF - Main Class.

// Arithmetic.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "FastHCF.h"

#include <iostream>
#include <vector>

using namespace std;

int main() {
    try {

        cout << "\n    Welcome to our demonstration sequels\n";
        cout << "Hope you enjoy (and follow) the lessons.\n\n";

        vector<unsigned> set;

        /*
        * Find HCF.
        */
        set = { 30, 48, 54 };

        // Use fast HCF
        FastHCF h_c_f(set);
        cout << "\n\n" << h_c_f.getHCF() << "\n";

    }    catch (exception& e) {
        cout << "\n" << e.what() << "\n";
    }
    return 0;
}

I have a better version / See other versions.