-->




Find Greatest Common Divisor (GCD) of two numbers c++ program

15 comments
What is GCD of two numbers?
It means a greatest number which divides both numbers
For example: Two numbers are 18 and 24
Numbers which divides both are 1, 2, 3 and  6 in which greatest number is 6 
So 6 is the GCD of 18 and 24 

Concept used: for loop, if statement
Post contains: 
  • C++ code
  • Program logic explanation
  • Variable values after each iteration (Dry run the code)
  • image view of code
  • sample output




#include<iostream>
using namespace std;

int main() {

int first_number;
cout<<"Enter First Number : ";cin>>first_number;

int  second_number;
cout<<"Enter Second Number: ";cin>>second_number;

int  gcd;
for(int i=1;i<=first_number&&i<=second_number;i++){


     if(first_number%i==&& second_number%i == ){

                     gcd=i;

   }

}

cout<<"Greatest Common Divison (GCD):"<<gcd<<endl;
return 0;
}






Logic Explanation:

  • Program takes input two numbers
  • A for loop which terminates if loop variable which is 'i'
    is greater than one of two numbers and operator is used to
    maintain this condition
  • Within for loop an if condition is used to check if variable 'i'divides both of them it will be saved in  GCD variable as value of 'i' is changing during each iteration in increasing order if another number divides both of them it will replace the previous value of GCD
  • After the loop termination our program will show the GCD of two number as the result


 Image view of code:

find GCD of two numbers c++ program
find GCD of two numbers c++ program

Sample output image view:





Sample input with dry run of code:
Let our sample input is 9 and 24

Values before loop
first_number=9 second_number=24

for i=1

   i<=9&&i<=24    condition is true

          9%1==0 && 24%1==0 true
  
                     GCD=1


for i=2 

   i<=9&&i<=24    condition is true

          9%2!=0 && 24%2==0   false
  
                     GCD=1
         
for i=3 

   i<=9&&i<=24    condition is true

          9%3==0 && 24%8==0 true

                     GCD=3
for i=4 

   i<=9&&i<=24    condition is true

          9%4!=0 && 24%4==0 false

                     GCD=3

for i=5 

   i<=9&&i<=24    condition is true

          9%5!=0 && 24%5!=0 false

                     GCD=3


for i=6 

   i<=9&&i<=24    condition is true

          9%6!=0 && 24%6==0 false

                     GCD=3


for i=7 

   i<=9&&i<=24    condition is true

          9%7!=0 && 24%7!=0 false

                     GCD=3


for i=8 

   i<=9&&i<=24    condition is true

          9%8!=0 && 24%8==0 false

                     GCD=3

for i=9 

   i<=9&&i<=24    condition is true

          9%9==0 && 24%!9=0 true

                     GCD=3


for i=10

   i<=9&&i<=24    CONDITION IS FALSE

Final output  :

Greatest Common Divison (GCD): 3

Recommended: Change the logic and do experiment with code 
for better understanding. 

15 comments:

  1. thank you for this help...........

    ReplyDelete
  2. Wonderful, beautiful program brotha.

    ReplyDelete
  3. You can see my c++ program to find the greatest common divisor
    http://www.mycodingland.com/2015/11/find-greatest-common-divisor-in-cpp-programming.html

    #include
    using namespace std;
    #include
    int main()
    {
    int x,y,m,i;
    cout<<"Insert Any Two Number: ";
    cin>>x>>y;
    if(x>y)
    m=y;
    else
    m=x;
    for(i=m;i>=1;i--)
    {
    if(x%i==0&&y%i==0)
    {
    cout<<"\nGCD of two number is : "<<i;
    break;
    }
    }
    getch ( );
    return 0;
    }
    // www.mycodingland.com //

    ReplyDelete
  4. plz give me this solution in break statement;;

    ReplyDelete
  5. plz give me this solution in break statement;;

    ReplyDelete
  6. Anyone can give an output like this please

    Enter first number:10
    Enter second number:8

    The gceof 10 and 8 is 2

    ReplyDelete