Competitive/Collaborative Programming Class

ICPC Computer Programming Contest Prep

Problem Solving in Computer Science

Fall 2022 -- CSC 2700 Section 01 (1216 Patrick Taylor, 6:00 PM - 7:50 PM)



GCD (Greatest Common Divisor)

I would usually approach something like GCD but prime fatoring both numbers and then multiply the matching prime factors. This will work, but it turns out that a much easier method exists.

The Euclidean algorithm is a very simple and fast algorithm for finding GCD. The original algoritm is based on repeated subtractions, but an improvement is to use the modulo (%) operation.

Here is a sample of a C snippet for GCD:
int gcd(int a, int b)
 { /* FUNCTION gcd */
   /* this uses Euclid's method */
   int toReturn;

   if (0 == b)
      toReturn = a;
   else
      toReturn = gcd(b, (a % b);
   return toReturn;
 } /* FUNCTION gcd */