9.12.2011

GCD or HCF of two numbers

Q. Write a C program for finding GCD of two given numbers.

Ans.

 /*c program for finding GCD/HCF of two numbers*/
 #include<stdio.h>
 #include<conio.h>
 int main()
 {
  int n1,n2,rem;
  printf("Enter first number : ");
  scanf("%d",&n1);
  printf("Enter second number : ");
  scanf("%d",&n2);
  if(n2>n1)
  {
    n1=n1+n2;
    n2=n1-n2;
    n1=n1-n2;
  }
  do{
      rem=n1%n2;
      n1=n2;
      n2=rem;
    }while(rem!=0);
  printf("\nGCD of two number is %d",n1);
  getch();
  return 0;
 }

/************** OUTPUT ***************
Enter first number : 65
Enter second number : 45


GCD of two number is 5
**********************************/

14 comments:

  1. wow great! its help me thanx

    ReplyDelete
  2. good program...

    ReplyDelete
  3. please I want to understand wht does this mean
    n1=n1+n2;
    n2=n1-n2;
    n1=n1-n2;

    ReplyDelete
    Replies
    1. @Khaoula Ali,
      It is swapping of number if second number is greater then first number.
      For example:
      num1 = 5
      num2 = 10

      As our condition: num2 > num1 is True so,

      n1=n1+n2 = 5+10 = 15 ; //now n1 value = 15
      n2=n1-n2 = 15-10 = 5 ; //now n2 value = 5
      n1=n1-n2 = 15-5 = 10 ; //now n1 value = 10

      So you can see that n1 and n2 value has been swap.

      Delete
    2. That means swapping(interchange) the values for example
      n1=45
      n2=65

      condition is n2>n1
      n1=n1+n2 -> n1=45+65=110 // now n1=110
      n2=n1-n2 -> n2=110-65=45 // now n2=45
      n1=n1-n2 -> n1=110-45=65 // now n1=65

      finally n1=65 , n2=45

      Delete
    3. n1 65 n2 45 then how the condition satisfie n2>n1 tell me fast

      Delete
    4. @Swathi,

      We can omit the if condition.
      The if condition ensure that first number (n1) should be always be bigger to second number.
      In this program if condition used because user can understand what is happening during the compiling.

      If you omit the "if condition" , it happens in do...while loop.

      Delete
  4. Replies
    1. @Khaoula Ali,

      "rem" is a variable that represent the reminder.
      For example:
      rem = 14%5 = 4

      Delete
  5. cant we write this program with while loop?

    ReplyDelete
  6. Replies
    1. @Swathi Kankata,

      We can set the condition according to required program and responsive result.

      If you change the condition in above "finding the GCD or HCF" program n1>n2 rather than n2>n1

      Then you should make this algorithm, set all related condition, cross check with putting the dummy data and run the program.

      Hope its helpful.

      Delete