# C Program Example to find GCD of Two numbers with Algorithm

## Algorithm

The Euclidean algorithm is a simple and efficient method to get the Greatest Common Divisor (GCD) of two integer number.

The largest number that divides both of the input number without a remainder will be the output.

Step By Step algorithm of GCD:

1. Take Two number - `number1` and `number2`
2. Continue a loop upto when `number1``number2`
• If number1 > number2
• number1 = number1 - number2
• else
• number2 = number2 - number1
3. GCD = number1

Here's an example of nth steps to get the GCD -

Step k Equation Quotient and remainder
0 1071 = q0 462 + r0 q0 = 2 and r0 = 147
1 462 = q1 147 + r1 q1 = 3 and r1 = 21
2 147 = q2 21 + r2 q2 = 7 and r2 = 0; algorithm ends

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````#include <stdio.h>

int main()
{
int number1, number2;

printf("Enter two numbers: ");
scanf("%d %d", &number1, &number2);

while(number1 != number2)
{
if(number1 > number2) {
number1 = number1 - number2;
} else {
number2 = number2 - number1;
}
}

printf("GCD = %d", number1);

return 0;
}``````
Copy The Code &

Input

cmd
15 45

Output

cmd
Enter two numbers: 15 45
GCD = 15

### #2 GCD ProgramExample C Program using Recursion

```Code - C Programming```

``````#include <stdio.h>

int gcd(int number1, int number2){
if(number2 == 0) {
return number1;
}

return gcd(number2, number1 % number2);
}

int main()
{
int number1, number2;

printf("Enter two positive integers: ");
scanf("%d %d", &number1, &number2);

printf("GCD = %d", gcd(number1, number1));

return 0;
}
``````
Copy The Code &

Input

cmd
15 45

Output

cmd
Enter two numbers: 15 45
GCD = 15

## Demonstration

C Program Example to find GCD of Two numbers with Algorithm