C++ program for gcd of two numbers

Logic:

We can solve this by recursion .

1.The base condition is that if both numbers are same let,s say x and y are equal we return either x or y.

2.else
                  
               * if x is greater than y we subtract y from x and then again call the function like this 
                              gcd(x-y,y)
               *else if y is greater than x we subtract x from y and then again call the function like this
                              gcd(x,y-x)

program:

#include<iostream>
using namespace std;
int gcd(int n1,int n2)
{
    if(n1==n2)
    {
        return n1;
    }
    if(n1>n2)
    {
        return gcd(n1-n2,n2);
    }
    return (n1,n2-n1);
    
}
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b);
}


output:

60 45                                                                                                                                          
15 

100 1050                                                                                                                                       
50                                                                                                                                             
           

40 80                                                                                                                                          
40                                                                                                                                             
         


Comments

Popular posts from this blog

c++ program to print string along the diagonals of the matrix.

Kollywood Game

C program to print the following Pattern