Find the Highest Common Factor (HCF) Using C++
This interactive lesson shows you how to find the Highest Common Factor (HCF) — also known as the Greatest Common Divisor (GCD) — using C++ with user input. By entering your own numbers, you can see how a simple C++ algorithm calculates the HCF step by step.
This activity combines mathematics and programming, making it ideal for students who are learning basic coding concepts alongside number theory.
What Is the Highest Common Factor (HCF)? | Maths Explanation for C++ Kids
The Highest Common Factor of two numbers is the largest number that divides both values exactly, without leaving a remainder. For example, the HCF of 12 and 18 is 6.
Understanding HCF helps students build strong foundations in:
- Factors and divisibility
- Problem-solving skills
- Logical and algorithmic thinking
Using C++ to Calculate HCF
In this example, C++ is used to create an interactive program that allows the user to enter several numbers. The program then checks which values divide both numbers evenly and identifies the highest one.
This approach demonstrates:
- How to accept user input in C++
- How loops can be used to test factors
- How math logic can be turned into working code
Understanding the HCF Algorithm in C++
This C++ algorithm solves the HCF (Highest Common Factor) using user input and
the Fast HCF C++ Code from the previous lesson.
Let's add some input mechanism so our user enters the set of
numbers whose H.C.F. (G.C.D.) we are to find.
Combining the H.C.F. (G.C.D.) C++ Code and Collecting User Input
The code follows the same steps as that from the previous lessons.
We just adapted the HCF.html
How to use the HCF Code in C++
The user gets to enter several numbers for the HCF C++ algorithm.
After entering each number, the user clicks the
Next Number! button to enter the next number.
After the user enters the last number, with the last
number still in the text box, the user clicks the
Find H.C.F. button.
How the C++ HCF Algorithm Works
The C++ HCF algorithm follows these simple steps:
-
1. Ask the user to enter several numbers.
2. Identify the smaller of the numbers.
3. Check each number from 1 up to the smaller value.
4. Find the largest number that divides all inputs exactly.
5. Display the result as the HCF.
This method is easy to understand and well suited for beginners learning how algorithms work.
HCF vs GCD Explained | Maths Explanation for C++ Kids
You may see both HCF (Highest Common Factor) and GCD (Greatest Common Divisor) used in math and programming. They mean the same thing—the largest number that divides two values exactly.
In C++ programming, both terms are commonly used when writing math algorithms.
Why Learn HCF Through C++?
Learning to calculate HCF using C++ helps students:
- Connect math concepts to real code
- Practice logical thinking and debugging
- Gain confidence with basic programming structures
- Learn by doing, not just reading
This makes it an excellent math coding project for primary and early secondary students.
Who Is This C++ HCF-with-input Algorithm Lesson For?
This interactive C++ HCF lesson is suitable for:
- Primary and junior secondary school students
- Teachers introducing coding with math
- Beginners learning C++ through practical examples
- Anyone interested in interactive math programming
Summary: HCF with User Input Algorithm in C++
This page demonstrates how to:
- Find the Highest Common Factor using C++
- Use user input to create an interactive program
- Apply math logic through a simple C++ algorithm
- Learn coding and mathematics together in a practical way
Try the example, explore the code, and use this project as a foundation for more advanced math and programming challenges.
So! C++ Fun Practice Exercise - Find HCF with User Input
As a fun practice exercise, feel free to try out your own numbers, and see how the C++ code finds the HCF of your input numbers.
C++ Code for Fast HCF - Header File.
#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 "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 HCF with User Input - Main Class.
//
#include "stdafx.h"
#include "FastHCF.h"
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <regex>
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;
// Collect input
cout << "\nWelcome to our Find HCF program.\n";
cout << "Enter your series of numbers whose HCF you wish to find.\n";
cout << "\nType 'done' when you are through with entering your numbers.\n";
cout << "Enter First Number: ";
set = {};
string user_input;
int user_num;
regex verify_num("([0-9]+)"); //Regular expression object
try {
do {
// get keyboard input
getline(cin, user_input);
// Convert 'user_input' to upper case.
transform(user_input.begin(), user_input.end(), user_input.begin(), ::toupper);
// Make sure input is a number
if (regex_match(user_input, verify_num)) {
stringstream(user_input) >> user_num;
if (user_num != 0) {
set.push_back(user_num);
cout << "Enter Next Number: ";
}
else {
cout << "\nYou cannot enter zero. Repeat that!\nType 'done' when you're finished.\n";
}
}
else if (user_input != "DONE") {
cout << "\nWrong Input. Repeat that!\nType 'done' when you're finished.\n";
}
} while (user_input != "DONE");
}
catch (exception& ex) {
throw "Bad Input";
}
// use the fast class to create object
FastHCF H_C_F(set);
cout << "\n" << H_C_F.getHCF() << "\n";
} catch (exception& e) {
cout << "\n" << e.what() << "\n";
}
return 0;
}