What is HCF and GCD? | Maths Explanation for C++ Kids
Highest Common Factor or Greatest Common Divisor is the highest-valued-factor
or greatest-valued-divisor common to a set of numbers.
In this C++ math project, we'll explore how to find the Highest Common Factor (HCF) and Greatest Common Divisor (GCD) of numbers.
This tutorial is perfect for primary school students learning to code with C++.
A common method for finding H.C.F. - G.C.D. is repeated factorization
using only common factors.
If we have the set of numbers 30, 48 and
54 for example, their H.C.F. or G.C.D. is found thus:
Hence, H.C.F. of 30, 48 and 54 = 2 X 3 = 6
How to find HCF of multiple numbers in C++ | Step-by-step Guide.
We shall follow the steps below in our C++ algorithm for finding HCF.
Step 1:
Do a numerical sort on the set so its first member is the smallest in the set.
Step 2:
Starting with 2, iteratively check through the set of numbers for a common factor.
Step 3:
For each common factor, divide every member of the number set by the common factor.
Step 4:
Repeat from step 2 recursively until there are no more common factors.
Create a new C++ class file;
Call it HCF.
Type out the adjoining C++ code for finding Highest Common Factor (H.C.F.) or Greatest Common Divisor.
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 - Find HCF
As a fun practice exercise, feel free to try out your own numbers, and see how the C++ code finds the HCF of those numbers.
C++ Code for HCF - Header File.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
class HCF {
public:
HCF(vector<unsigned>);
virtual ~HCF();
unsigned getHCF(void);
private:
int HCFFactors(void);
int * set_of_numbers;
size_t array_length;
vector<unsigned> common_factors; // factors common to our set_of_numbers
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 HCF - Class File.
#include "HCF.h"
HCF::HCF(vector<unsigned> group) {
common_factors = {};
group.shrink_to_fit();
array_length = group.size();
set_of_numbers = new int[array_length];
index = 0;
sort(group.begin(), group.end());
//iterate through and retrieve members
for (int number : group) {
set_of_numbers[index] = number;
index++;
}
index = 2;
all_round_factor = false;
}
/**
* Our function checks 'set_of_numbers'; If it finds a factor common to
* all for it, it records this factor; then divides 'set_of_numbers' by the
* common factor found and makes this the new 'set_of_numbers'. It
* continues recursively until all common factors are found.
*/
int HCF::HCFFactors() {
while (index <= set_of_numbers[0]) {
// Check for factors common to every member of 'set_of_numbers'
all_round_factor = true;
for (int j = 0; j < array_length; j++) {
if (!(all_round_factor == true && (set_of_numbers[j] % index) == 0)) {
all_round_factor = false;
}
}
// Divide every member of 'set_of_numbers' by each common factor
if (all_round_factor == true) {
for (int j = 0; j < array_length; j++) {
set_of_numbers[j] /= index;
}
common_factors.push_back(index);
return HCFFactors();
}
index++;
}
return 0;
}
/**
* Just calls out and collects the prepared factors.
* @param - None.
*/
unsigned HCF::getHCF() {
HCFFactors();
common_factors.shrink_to_fit();
//iterate through and retrieve members
calc_result = 1;
for (unsigned factor : common_factors) {
calc_result *= factor;
};
return calc_result;
}
HCF::~HCF() {
delete[] set_of_numbers;
}
C++ Code for HCF - Main Class.
//
#include "stdafx.h"
#include "HCF.h"
#include <iostream>
#include <vector>
#include <sstream>
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.
*/
string render_result = "The HCF of ";
stringstream aux;
set = {30, 48, 54};
for (int number : set) {
aux.str("");
aux << number;
render_result += aux.str() + "; ";
}
render_result += "is: ";
HCF hcf(set);
cout << "\n\n" << render_result << hcf.getHCF() << "\n";
} catch (exception& e) {
cout << "\n" << e.what() << "\n";
}
return 0;
}