In this C program, we will find GCD (Greatest Common Divisor) of two numbers using for loop. The highest common factor (HCF) of two or more integers, is the largest positive integer that divides the numbers without a remainder.
HCF is also known as greatest common divisor (GCD) or greatest common factor(GCF)
Required Knowledge
Algorithm to find GCD of two numbers
Let, A and B are two numbers.
Let, A and B are two numbers.
- Find minimum of A and B. Let A < B.
- Find the largest number between 1 to A, which divides A and B both completely.
C program to find gcd of two numbers using for loop
#include <stdio.h>
int getMinimum(int a, int b){
if(a >= b)
return b;
else
return a;
}
int main() {
int a, b, min, counter, gcd = 1;
printf("Enter two numbers\n");
scanf("%d %d", &a, &b);
min = getMinimum(a, b);
for(counter = 1; counter <= min; counter++) {
if(a%counter==0 && b%counter==0) {
/* Update GCD to new larger value */
gcd = counter;
}
}
printf("GCD of %d and %d = %d\n", a, b, gcd);
return 0;
}
Output
Enter two numbers 15 50 GCD of 15 and 50 = 5Related Topics