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 