ECE 150 Fundamentals of programming

Write a function that calculates the greatest common divisor, as described in the course notes, and the least common multiple. When calculating the least-common multiple, the easiest is to use the formula ${\rm lcm}(m, n) = \frac{mn}{\gcd(m,n)}$. The function declarations are:

unsigned long gcd( unsigned long m, unsigned long n );
unsigned long lcm( unsigned long m, unsigned long n );

There is a problem here, however, as the calculation $mn$ may overflow, while the result is never-the-less storable as an unsigned long.

For example, your code should work with:

#include <iostream>

unsigned long gcd( unsigned long m, unsigned long n );
unsigned long lcm( unsigned long m, unsigned long n );
int main();

int main() {
    unsigned long m{17217616477};
    unsigned long n{31097282059};

    std::cout << gcd( m, n ) << std::endl;
        // Should output 15525353
    std::cout << lcm( m, n ) << std::endl;
        // Should output 34486885803431

    return 0;
}

Your program should throw a std::range_error if the least common multiple cannot be stored as an unsigned long; for example, the following code should generate an exception:

#include <iostream>
#include <stdexcept>

unsigned long gcd( unsigned long m, unsigned long n );
unsigned long lcm( unsigned long m, unsigned long n );
int main();

int main() {
    unsigned long m{4294967311};  // 203280222nd prime number
    unsigned long n{4294967357};  // 203280223rd prime number

    std::cout << gcd( m, n ) << std::endl;
        // Should output 1

    try {
        std::cout << lcm( m, n ) << std::endl;
            // This should generate an exception
    } catch ( std::range_error &e ) {
        std::cout << e.what() << std::endl;
    }

    return 0;
}