Lets write a C program to find Greatest Common Divisor of two positive integer numbers using repeated subtraction.
Related Read:
C Program to Find GCD or HCF of Two Numbers
C Program To Find GCD and LCM of Two Numbers using Euclidean algorithm
C Program To Find GCD using Pointers and Functions
Video Tutorial: C Program To Find GCD using Repeated Subtraction
[youtube https://www.youtube.com/watch?v=sv8Jehsydrs]
Source Code: C Program To Find GCD using Repeated Subtraction
#include<stdio.h>
int main()
{
int num1, num2;
printf("Enter 2 positive integer numbers\n");
scanf("%d%d", &num1, &num2);
num1 = (num1 < 0) ? -num1 : num1;
num2 = (num2 < 0) ? -num2 : num2;
printf("\nGreatest Common Divisor of %d and %d is ", num1, num2);
while(num1 != num2)
{
if(num1 > num2)
{
num1 = num1 - num2;
}
else
{
num2 = num2 - num1;
}
}
printf("%d.\n", num1);
return 0;
}
Output 1:
Enter 2 positive integer numbers
20
30
Greatest Common Divisor of 20 and 30 is 10.
Output 2:
Enter 2 positive integer numbers
1980
1617
Greatest Common Divisor of 1980 and 1617 is 33.
Logic To Find GCD using Repeated Subtraction
Lets assume that num1 = 15 and num2 = 20. Lets calculate GCD for these 2 numbers.
While loop iterates until num1 is equal to num2.
| num1 | num2 | Greater No | Subtract Numbers | Result |
|---|---|---|---|---|
| 15 | 20 | num2 = 20 | num2 = num2 – num1 | num2: 20 – 15 = 5 |
| 15 | 5 | num1 = 15 | num1 = num1 – num2 | num1: 15- 5 = 10 |
| 10 | 5 | num1 = 10 | num1 = num1 – num2 | num1: 10- 5 = 5 |
| 5 | 5 | Both Are Equal | num1 == num2 | GCD is 5. |
You can see below code in the C program i.e., converting a negative number into positive. Our source code above works only for positive integer numbers without this code. If the user enters negative value we use ternary operator to make it a positive value.
num1 = (num1 < 0) ? -num1 : num1;
num2 = (num2 < 0) ? -num2 : num2;
Here we check if num1 is less than 0. If true, then value of num1 is negative. So we multiply the number by -, which gives us a positive number. For example, if num1 is -15, then -(-15) is +15.
Ternary Operator / Conditional Operator In C
You can make use of simple if else statement like below, to convert negative number into positive:
#include<stdio.h> if(num1 < 0) num1 = num1 * -1; if(num2 < 0) num2 = num2 * -1;
That would convert a negative number to positive number.
While Loop
While loop iterates until num1 is not equal to num2. Once num1 is equal to num2, control exits while loop. Whatever is present in num1 or num2 is the GCD of 2 positive integer numbers entered by the user.
Inside while loop, we check if num1 is greater than num2. If true, we subtract num2 from num1 and store it back inside variable num1. Else if num2 is greater than num1, then we subtract num1 from num2 and store it back inside num2. We repeat this until num1 is equal to num2.
For list of all c programming interviews / viva question and answers visit: C Programming Interview / Viva Q&A List
For full C programming language free video tutorial list visit:C Programming: Beginner To Advance To Expert