The G.C.D. (Greatest Common Divisor) or H.C.F (Highest Common Factor) of number is the largest positive integer that perfectly divides the two given number.
gcd(m,n) is designed as the most common divisor of two nonnegative, not both zero integers m and n that divides both evenly.
One of Euclidean volumes, most famous for its systematic presentation of geometry, outlines and algorithm for solving the problem of gcd. Modern terms, Euclidean algorithm includes applying equality repeatedly.
gcd(m,m) = gcd(n,m mod n)
Euclidean algorigthm for computing gcd(m, n)
We can express the same algorithm in a pseudocode (Euclidean Pseudocode)
// computes gcd(m, n) by Euclidean algorithm
// Input: Two non-negative, not-both-zero integers m and n.
// Output: Gretaest common divisor of m and n.
while n == 0 do
rem <- m mod n
m <- n
n <- r
return m
#include <stdio.h>
// Define the function to calculate the GCD
int gcd(int m, int n){
if(n == 0){
return m; // if n == 0 then return the value of m
}
return gcd(n, m % n);
}
int main()
{
int m, n;
printf("Enter the first number : ");
scanf("%d", &m);
printf("Enter the second number : ");
scanf("%d", &n);
int GCD;
// Check the greater value of the give number by user.
if(m < n){
GCD = gcd(n, m);
}else{
GCD = gcd(m, n);
}
printf("GCD is : %d", GCD); // print the value of final GCD after calculation of two number
return 0;
}
#include <iostream>
using namespace std;
int gcd(int m, int n){
if(n == 0){
return m;
}
return gcd(n, m % n);
}
int main()
{
int m, n;
cout<<"Enter the first number : ";
cin>>m;
cout<<"Enter the second number : ";
cin>>n;
int GCD;
if(m < n){
GCD = gcd(n, m);
}else{
GCD = gcd(m, n);
}
cout<<"GCD is : "<< GCD;
return 0;
}
Consecutive integer checking algorithm for computing gcd(m,n)
#include<stdio.h>
int gcd(int m, int n){
if(n == 0){
return m;
}
int isFind = 0;
int gcD;
int t = n;
while(isFind == 0){
if(m % t == 0){
gcD = t;
if(n % gcD == 0){
isFind = 1;
}
}
t--;
}
return gcD;
}
int main(){
int m = 60;
int n = 24;
int gcdAns = gcd(m, n);
printf("GCD is : %d", gcdAns);
return 0;
}
#include<iostream>
using namespace std;
int gcd(int m, int n){
if(n == 0){
return m;
}
int isFind = 0;
int gcD;
int t = n;
while(isFind == 0){
if(m % t == 0){
gcD = t;
if(n % gcD == 0){
isFind = 1;
}
}
t--;
}
return gcD;
}
int main(){
int m = 60;
int n = 24;
int gcdAns = gcd(m, n);
cout<<"GCD is : "<<gcdAns;
return 0;
}
GCD calculate by the prime factors of the number.
For Example: Thus, for the number 60 and 24, we get
60 = 2, 2, 3, 5
24 = 2, 2, 2, 3
gcd(60, 24) = 2, 2, 3 = (2 * 2 * 3) = 12
#include<stdio.h>
int main(){
int m, n, gcd, i;
printf("Enter the first number : ");
scanf("%d", &m);
printf("Enter the second number : ");
scanf("%d", &n);
for(i=1; i <= m && i <= n; ++i)
{
if(m%i==0 && n%i==0)
gcd = i;
}
printf("GCD : %d", gcd);
return 0;
}
#include<iostream>
using namespace std;
int main(){
int m, n, gcd, i;
cout<<"Enter the first number : ";
cin>>m;
cout<<"Enter the second number : ";
cin>>n;
for(i=1; i <= m && i <= n; ++i)
{
if(m%i==0 && n%i==0)
gcd = i;
}
cout<<"GCD : "<<gcd;
return 0;
}
Comments
Oops!