GCD By Factoring

November 3, 2017

We begin with this function that extracts common items from two sorted lists by simply walking down the lists:

(define (common lt? xs ys)
  (let loop ((xs xs) (ys ys) (zs (list)))
    (cond ((or (null? xs) (null? ys)) (reverse zs))
          ((lt? (car xs) (car ys)) (loop (cdr xs) ys zs))
          ((lt? (car ys) (car xs)) (loop xs (cdr ys) zs))
          (else (loop (cdr xs) (cdr ys) (cons (car xs) zs))))))

For instance, (common < '(2 3 4 5 6) '(1 3 5 7 9)) returns the list (3 5). Then it’s easy to compute the greatest common divisor of two numbers:

(define (gcd-by-factoring m n)
  (apply * (common < (factors m) (factors n))))

This reads just as the english-language description of the problem; take the product of the common prime factors of the two numbers. Here are some examples:

> (gcd-by-factoring 24 60)
12
> (gcd-by-factoring 11111111 13290059)
1

You can run the program at https://ideone.com/v4xIrv, where you will also find a simple factoring program, suitable for finding small factors of not-too-large numbers.

When programming, either for myself or for the blog, I often look for reusable functions that I can extract from a program. For example, I could have written gcd-by-factoring with the code for common embedded within it, but separating the code yields a function that is useful in other contexts.

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: