GCD of two numbers- how to find with programming C

Question: Write a program to find Greatest Common Divisor(GCD) of two numbers using recursion.

Explanation:

Rule 01: if(b==0) return GCD(a,b)=a;

Rule 02: else if(a>b)  return GCD(a,b)=GCD(b,a);

 Rule 03: else return GCD(a,b%a);

You can also see for video explanation

a=3 b=5
GCD(3,5) = GCD(3, 2) Rule 03
GCD(3,2)=GCD(2,3) Rule 02
GCD(2,3)=GCD(2,1) Rule 03
GCD(2,1)=GCD(1,2) Rule 02
GCD(1,2)=GCD(1,0) Rule 03
GCD(1,0) = 1 Rule 01

Program:

<include<bits/stdc++.h>

int GCD(int,int); ///Function Prototype

int main()
{
int a,b,result;
while(scanf(“%d %d”,&a,&b)==2)
{
result=GCD(a,b); ///Function Calling
printf(“GCD of %d and %d is: %d\n”,a,b,result);
}
return 0;
}
int GCD(int p,int q) ///Function/Recursion Definition
{
if(q==0)
return p;
else if(p>q)
return GCD(q,p);
else
return GCD(p,q%p);

return -1;
}

Share

2 thoughts on “GCD of two numbers- how to find with programming C

  1. Good – I should certainly pronounce, impressed with your website. I had no trouble navigating through all tabs and related information ended up being truly easy to do to access. I recently found what I hoped for before you know it at all. Reasonably unusual. Is likely to appreciate it for those who add forums or something, website theme . a tones way for your customer to communicate. Excellent task..

Leave a Reply

Your email address will not be published. Required fields are marked *

Proudly powered by WordPress | Theme: Lean Blog by Crimson Themes.