Go to Top

Thursday 4 August 2011

To find the GCD or HCF of two numbers

Question 36 : Write a program in Java to find the Greatest Common Divisor (G.C.D.) of two numbers entered by the user : 


Java Program : 


import java.io.*;
class hcf
{
 static void main()throws IOException
 {
     BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
     int a,b,i;
     int d=1;
     int c=0;
     System.out.print("Enter the first number : ");
     a=Integer.parseInt(br.readLine());
     System.out.print("Enter the second number : ");
     b=Integer.parseInt(br.readLine());
     if (a>b)
     c=a;
     else
     c=b;
     for(i=1;i<=c;i++)
     {
        if (a%i==0 && b%i==0 && i>d)
        d=i;
    }
    System.out.println("The H.C.F. = "+d);
}
}

32 comments:

  1. Thanks for your program.I could not understand why
    d=1.If i want to take GCD of 6 and 12 then the common factors will be 1,2,3,6.WHY COMPUTER is taking 6 as answer when d=1 as i is greater than 1

    ReplyDelete
    Replies
    1. This program is created to find out the largest common factor,not all the factors.
      GCD = greatest common factor...simple.

      Delete
  2. Thanks for the program.

    ReplyDelete
  3. Good work but pretty tough for me to understand

    ReplyDelete
  4. Use the comment lines. Its is hard to understand for a begineer.... btw nice blog... :)

    ReplyDelete
  5. if (a%i==0 && b%i==0 && i>d) i need more ang wider explanation about this code.

    ReplyDelete
    Replies
    1. a%i == 0 && b%i==0 checks for common factors. i>d ensures it is not 1.but still we can skip i > d. as it is in loop so d would store the GCD

      Delete
  6. Good one but unnecessary processing.
    " if(a>b)
    c=a;
    else
    c=b;
    for(i=1;i<=c;i++) "
    why not go from 1 to the (smaller number)/2 (instead of greater) since HCF can never be greater than half of the smaller number

    ReplyDelete
  7. "HCF can never be greater than half of the smaller number" is a wrong statement as HCF of 100 and 50 is 50.

    ReplyDelete
    Replies
    1. but still why should we take greater of both . why not the smaller on

      Delete
  8. Hello... why is " if (a%i==0 && b%i==0) " used.
    what is the meaning of this statement...
    Could anyone help me out????

    ReplyDelete
    Replies
    1. Check my reply to the Anonymous 10 July 2013

      Delete
    2. The condition checks if the number I divides both the numbers a and b or not ! A gcd should divide both the numbers !

      Delete
  9. without knowing what is GCD..how can u write the code..First learn what GCD is & then try to code.

    ReplyDelete
  10. Thanx for d program....its very helpful....@ blogger...

    ReplyDelete
  11. Computing the Greatest Common Divisor (GCD) or Highest Common Factor (HCF) of two numbers Fix Device Streaming is a fundamental mathematical task.

    ReplyDelete

ShareThis