//.........................................................................
//-------------------------------------------------------------------------
//------------THE PROGRAM TO FINd GCD OF TWO POSITIVE INTEGERS-------------
//-----------------------THE JAVA CODE STARTS HERE-------------------------
//--------THE DEVELOPMENT OF ALGORITHM IS GIVEN AT THE END-----------------
//.........................................................................
cclass gcd1
{
    public static void main(String args[])
    {
        long num1 = 1234500000L;
	long num2 = 42;
	long small,big;   // variables to manipulate num1 and num2
	small = num1;
	big = num2;
	long temp;
	// in order to ensure that small<=big, we execute the following
        // if statement

	if(small>big)
	    {
		temp = small;
		small = big;
		big = temp;
	    }
	// at this stage small<=big. We now write the iterative code for
        // computing the gcd of the two numbers.

	while(small!=big)
	    {
		temp = big-small;
		if(temp<small)
		    { 
			big = small;
			small=temp;
		    }
		else
		    big = temp;
	    }
	System.out.println(" GCD of "+num1+" and "+num2+" is : "+small);
    }
}
//.........................................................................
//-------------------------------------------------------------------------
//------------------Algorithm Development for the GCD problem-------------
//.........................................................................
//
//DEFINITION : for any two integers x and y, gratest common divisor (GCD)
//is the largest possible integer which divides both x and y simultaneously.
//
//Aim is to write a program to compute GCD of two given integers x and y.
//
// If one of x and y is zero, then the another number is the GCD since every 
// number divides zero. So from now onwards we assume that both x and y are 
// positive integers. Furthermore, let x>=y.
//
// Observation1 : If x=y, then GCD is x itself.
//
// What can we say if x and y are different ?
//
// Observation2 : If r divides x as well as y, then r also divides x-y also.
// Hence GCD(x,y)=GCD(x-y,y)
//
// How can we use the above observation to design an algorithm to compute GCD 
// of two numbers.
//
// If $x==y$, then report x as GCD
// else
// we can conclude that GCD(x,y) is same as GCD(r,y);
//
// Let us consider a specific example. GCD of 6,14
//
// x=14, y=6
// ----------
// r=x-y=8
// x=8,y=6
// ---------
// r=x-y=2
// x=6,y=2
// ---------
// r=x-y=4
// x=4,y=2
// ---------
// r=x-y=2
// x=2,y=2
// --------
// stop.
//
// Why is it an algorithm ? 
// In particular, will it take finite number of steps?
// Yes, this is because, the value of one of the number reduces in each 
// iteration. The numbers always remain positive. So after at most x steps,
// the algorithm will terminate.
//
// How to write the program based on the above algorithm. One important thing
// to note here is that we execute a sequence of similar tasks in the 
// algorithm. So we should try to write a loop for executing the algorithm.
// 
// The condition for the loop will be (x!=y) because we stop as soon as x==y.
// 
// In each iteration we do r=x-y;
// then x=r;
//
// There is a problem. The property that x>=y may not hold if we assign r to x.
// You can verify it from the specific example given above. 
// So precise set of statements inone iteration will be 
//  if(r<y) 
//  {
//     x=y;
//     y=r;
//  } 
//  else
//   x=r;
//
// The complete program is given above. Study it and understand it fully.
// The program is very inefficient. For example, for input with 
// num1=1234567800000000, and num2=42, the program will take ENORMOUS TIME. 
// Try it out on your own. The program is correct but it is not efficient.
// For a more efficeint algorithm read gcd2.java.
//