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