GCD of Two Numbers in C
Hello and Welcome to www.TechWithCode.com
The World of Computer Science and Technology
Today we will learn about how to write a C Program to find the GCD of Two Numbers. Before moving forward, we must have knowledge about what GCD is?
What is GCD?
GCD stands for Greatest Common Divisor.
GCD of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted {gcd(x,y)}.
For example, the GCD of 8 and 12 is 4, that is, {gcd(8,12)=4}
In order to find GCD, two scenarios occurred,
1. Find GCD of two numbers
2. Find GCD of Multiple Numbers (n Numbers)
Today we will write c programming code for both the scenarios one by one
To understand these Programs, you should have knowledge of the following C programming topics:
1. Find GCD of two numbers
Problem Statement⤵️
Write a C program that calculates the GCD of two numbers, this number should be taken as input from the keyboard.
Source code⤵️
#include <stdio.h>
int hcf(int n1, int n2);
int main() {
int n1, n2;
printf("Enter two positive integers: ");
scanf("%d %d", &n1, &n2);
printf("G.C.D of %d and %d = %d", n1, n2, hcf(n1, n2));
return 0;
}
int hcf(int n1, int n2) {
if (n2 != 0)
return hcf(n2, n1 % n2);
else
return n1;
}
output⤵️
2. Find GCD of Multiple Numbers (n Numbers)
Problem Statement⤵️
Write a C program that calculates the GCD of Multiple Numbers or N numbers, this number should be taken as input from the keyboard.
Source code⤵️
#include<stdio.h>
int main()
{
int x, y =- 1;
printf("Enter numbers. To Calculate Enter 0\n");
while(1) // infinite loop to take input
{
scanf("%d", &x);
if(x < 1)
break;
else if(y ==- 1) // only 1 number entered, its GCD is itself
y = x;
else if(x < y)
y = gcd(x, y);
else
y = gcd(y, x);
}
printf("\n\n\nGCD of all the entered number is: %d", y);
return 0;
}
// GCD of 2 numbers is calculated at a time
int gcd(int a, int b)
{
int i;
/*
a is the smallest of the two numbers
of which GCD is to be calculated
*/
for(i = a; i >= 1; i--)
{
// Greatest number that divides both the numbers
if(a%i == 0 && b%i == 0)
break; // exits the loop
}
return i;
}
No comments:
Do not add any link in the comments.
For backlink, contact us.