//.........................................................................
//-------------------------------------------------------------------------
//------MORE EFFICIENT PROGRAM TO FINd GCD OF TWO POSITIVE INTEGERS--------
//-----------------------THE JAVA CODE STARTS HERE-------------------------
//--------THE DEVELOPMENT OF ALGORITHM IS GIVEN AT THE END-----------------
//.........................................................................
cclass gcd2
{
    public static void main(String args[])
    {
        long num1 = 1007199254740998L;
	long num2 = 42;

	long small,big; // variables to manipulate num1 and num2
	small = num1;   
	big = num2;
	long temp=0;  
        // 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(big%small!=0)
	    {
		temp = big%small;
		big = small;
		small=temp;
	    }
	System.out.println(" GCD of "+num1+" and "+num2+" is : "+small);
    }
}

//.........................................................................
//...............THE DEVELOPMENT OF THE ALGORITHM IS GIVEN BELOW...........
//.........................................................................
//  Having realized that gcd1.java is a correct but an inefficient program, 
//  we need to design efficient algorithm for finding GCD of two numbers. 
//  We start with the following simple Theorem which you might have seen in 
//  your high school.
//  .......................................................................
//  Theorem : For any two positive integers x and y, there exist two unique
//  integers r and d such that
//  x = r*y + d, where d<y
//  .......................................................................
//  It follows easily from the Theorem that if z divides x as well as y, then
//  it must divide d also. (Try to give reason for it)
//  If y divides x, then y is GCD(x,y).
//  Otherwise if y does not divide x, then GCD(x,y) is the same as GCD(y,d)
//  where d is x%y. In this way we proceed to find GCD of x and y.
//  Let us work on a specific example now.
//    x=20
//    y=14
//   --------------
//    r=20%14=6
//    x=14
//    y=6  
//   --------------
//    r=x%y=2
//    x=6
//    y=2
//   --------------
//    x%y==0 so stop and report that 2 os GCD of 20 and 14.
//    
//   The argument that the above algorithm takes finite number of steps
//   is similar to that of gcd1.java. However, in this  algorithm, the number
//   of steps will be exponentially smaller than that of gcd, and hence
//   it will be more efficient. 
//   Again observe that the method outlined above is executing
//   a number of similar tasks, so we should write a loop for implementing.
//   this method in JAVA. 
//   What should be the stopping condition ?
//   Well, as soon as x%y become same, we should stop.
//   So the condition of the While loop will be (x%y!=0)
//   The complete program is written above. Please go through it and fully 
//   intenalize it 
//
//