Sunday, January 25, 2015

Euclid's Algorithm for Calculating GCD of two Integers [Java Implementation]

Tutorial on the Algorithm : http://www.rit.edu/~w-asc/documents/services/resources/handouts/DM%20-%206%20Euclidean%20Algorithm.pdf

Source:

public class EuclidGCD {
    public static int findGCD(int a, int b){  
        if(a==0)return b;
        if(b==0)return a;
        
        if(a<0)a=-a;
        if(b<0)b=-b;
        
        int min = Math.min(a, b);
        int max = a;
        if(min==a)max = b;
       
        int t, rem = t = min;
        
        while(t!=0){
            rem = t;
            t = max%min; 
            max = min;
            min = t; 
        }
        return rem;
    }
    
    public static void main(String[] args) throws Exception{ 
        System.out.println(findGCD(4278, 8602));
    } 
}

Output:

46

No comments:

Post a Comment