- Full Information About Artificial Intelligence | What is AI?
- Most Common Important 70+ Shortcut Keyboard Keys
- Stars Square Pattern
- Fascinating Number or Not in C and CPP
- Implement queue using linked list c program
- Calculate the GCD | Euclidean algorithm | c and cpp programming language
- Linear search in c | Algorithm of Linear search | c programming
- A C program for checking whether a given line is a comment
- C program to convert decimal to binary without array
- Voting program in C language using switch case
- C program to check eligible for vote
- Insertion and deletion in double linked list in c program
- File read in C | File Handling | How to read File
- C program to replace vowels with special characters
- Call by Reference in C programming language
- Function call by value in c programming language
- Program to print a message without using semicolon in c programming
- User login system in c programming language
- How to make swastik in c and cpp programming language
- Print numbers from 1 to 100 using while loop c and cpp program
- Simple Macro Substitution(#define) in c and cpp programming language
- Insertion and Deletion of all operation at singly Linked list in c programming langauge
- Write a program to count the digit in a number
- Program to calculate the power of given numbers by user in c and cpp
- Sum of digit calculate program
- Write a program to reverse a number
- Floyd Triangle | Programs | Algorithm
- Program to check whether number is Disarium Number
- Sunny Number in programming
- Happy Number | with Example and Programs
- Display Name of the month by accepting digit of the month | c programming
- Spy Number | c programming
- 9 basic program in cpp programming language
- Automorphic number | c programming language
- C programming restaurant menu code lapmos
- Neon Number c programming language
- Strong Number in C programming What is Strong Number
- Leap Year | Leap year program in c
- Pascal Triangle C programming
- Check Palindrome Number in c
- Print Fibonacci Series in c
- Swap two number without using third variable c programming langauge
- Swap two number c programming
- Largest Number c programming language
- Prime number program in c
- What is the mean by Software Engineering?

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)

- If n == 0, return the value of m as the answer and stop; other proceed to step 2.
- Divide m by n and assign the value of the remainder to rem.
- Assign the value of n to m and the value of rem to n. Go to Step 1.

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)

- Assign the value of min(m,n) to t.
- Divide m by t. If the remainder of this division is 0, go to step 3; otherwise, go to step 4.
- Divide n by t. If the remainder of this division is 0, return the value of t as the answer and stop.
- Decrease the value of t by 1. Go to step 2.

```
#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.

- Find the prime factors of m.
- Find the prime factors of n.
- Identify all the common factors in the two prime expansions found in step 1 and step 2. (If p is a common factor occuring p
_{m }and p_{n }times in m and n, respectively, it should be repeated min(p_{m}, p_{n}) times. - Compute the product of all the commong factors and return in as the greatest common divisor of the numbers given.

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;
}
```

ðŸ–¤ 0

Buy me coffee â˜•

## Comments

Oops!