Program to find GCD or HCF of two numbers using Middle School Procedure in C++
-
10-09-2020 - |
Question
In this tutorial, we will be discussing a program to find GCD or HCF of two numbers using Middle School Procedure.
For this we will be provided with two numbers. Our task is to find the GCD (greatest common divisor) or HCF (highest common factor) for the given values.
Example
#include <bits/stdc++.h> #define MAXFACTORS 1024 using namespace std; //structure to store factorization typedef struct{ int size; int factor[MAXFACTORS + 1]; int exponent[MAXFACTORS + 1]; } FACTORIZATION; void FindFactorization(int x, FACTORIZATION* factorization){ int i, j = 1; int n = x, c = 0; int k = 1; factorization->factor[0] = 1; factorization->exponent[0] = 1; for (i = 2; i <= n; i++) { c = 0; while (n % i == 0) { c++; n = n / i; } if (c > 0) { factorization->exponent[k] = c; factorization->factor[k] = i; k++; } } factorization->size = k - 1; } //printing the factors void DisplayFactorization(int x, FACTORIZATION factorization){ int i; cout << "Prime factor of << x << = "; for (i = 0; i <= factorization.size; i++) { cout << factorization.factor[i]; if (factorization.exponent[i] > 1) cout << "^" << factorization.exponent[i]; if (i < factorization.size) cout << "*"; else cout << "\n"; } } //gcd using Middle School procedure int gcdMiddleSchoolProcedure(int m, int n){ FACTORIZATION mFactorization, nFactorization; int r, mi, ni, i, k, x = 1, j; FindFactorization(m, &mFactorization); DisplayFactorization(m, mFactorization); FindFactorization(n, &nFactorization); DisplayFactorization(n, nFactorization); int min; i = 1; j = 1; while (i <= mFactorization.size && j <= nFactorization.size) { if (mFactorization.factor[i] < nFactorization.factor[j]) i++; else if (nFactorization.factor[j] < mFactorization.factor[i]) j++; else{ min = mFactorization.exponent[i] > nFactorization.exponent[j] ? nFactorization.exponent[j] : mFactorization.exponent[i]; x = x * mFactorization.factor[i] * min; i++; j++; } } return x; } int main(){ int m = 10, n = 15; cout << "GCD(" << m << ", " << n << ") = " << gcdMiddleSchoolProcedure(m, n); return (0); }
Output
GCD(10, 15) = Prime factor of << x << = 1*2*5 Prime factor of << x << = 1*3*5 5
Not affiliated with Tutorialspoint