GCD By Factoring

November 3, 2017

Regular readers of this blog know that Euclid’s algorithm, dating to 300 B.C., is the standard algorithm for computing the greatest common divisor of two numbers. But middle school teachers have their students calculate the greatest common divisor by factoring the two numbers and taking the product of the prime factors they have in common, being careful to count multiplicities correctly.

Your task is to write a program that calculates greatest common divisors by factoring. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Pages: 1 2

3 Responses to “GCD By Factoring”

  1. Paul said

    Two functions in Python. The first looks at the common factors of the 2 numbers. The second first gets the factors of the first number and then tries these factors on the second number.

    def gcdf(a, b):
        common = Counter(td_factors(a)) & Counter(td_factors(b))
        gcd = 1
        for v, n in common.items():
            gcd *= v ** n
        return gcd
    
    def gcdf2(a, b):
        factors_of_a = Counter(td_factors(a))
        gcd = 1
        for f in factors_of_a.elements():
            if b % f == 0:
                b //= f
                gcd *= f
        return gcd
    
  2. Victoria said

    In Java
    long version:

    import java.util.ArrayList;
    
    public class GreatestDivisor {
    	public static void main(String[] args) {
    		
    		int a = 24, b = 60;
    		
    		ArrayList<Integer> list1 = new ArrayList<>(findDivisors(a));
    		ArrayList<Integer> list2 = new ArrayList<>(findDivisors(b));
    		ArrayList<Integer> list3 = new ArrayList<>();
    		
    		for(int x : list1) {
    			if(list2.contains(x)) list3.add(x);
    		}
    		int max = list3.get(0);
    		
    		for(int x=0; x<list3.size(); x++) {
    			if(max < list3.get(x)) max = list3.get(x);
    		}
    		
    		System.out.format("The greatest divisor of %d and %d is %d.", a, b, max);
    		
    	}
    	
    	public static ArrayList<Integer> findDivisors(int i) {
    		ArrayList<Integer> list = new ArrayList<>();
    		for(int x=1; x<=i; x++) {
    			if(i%x == 0) list.add(x);
    		}
    		return list;
    	}
    
    }
    
  3. Victoria said

    Java short version:

    public class GCDEuclidian {
    	public static void main(String[] args) {
    		int a = 60;
    		int b = 24;
    		int max = Math.max(a, b);
    		int min = Math.min(a, b);
    		
    		while(min != 0) {
    			int holdMin = min;
    			min = max%min;
    			max = holdMin;
    			
    			if(min == 0) System.out.println(max);
    		}	
    	}
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: