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.
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 gcdIn 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; } }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); } } }