The greatest common factor, or gcd, of two integers $m$ and $n$ is the largest positive integer $k$ such that $\frac{m}{k}$ and $\frac{n}{k}$ are both integers.

The least common multiple, or lcm, of two integers $m$ and $n$ is the smallest positive integer $k$ such that $\frac{k}{m}$ and $\frac{k}{n}$ are both integers.

We have described the Euclidean algorithm for computing the gcd. We will now consider algorithms for calculating the lcm.

The brute force algorithm is to calculate multiples of one number until that product is divisible by the second number. This algorithm, however, has one simple advantage: you never make an intermediate calculation that is larger than the result.

The standard algorithm is that ${\rm lcm}(m, n) = \frac{mn}{\gcd(m,n)}$; however, this has the disadvantage that if the gcd is very large, then the product $mn ≫ {\rm lcm}(m, n)$, so this may cause an overflow. It is therefore critical that the calculation is $\frac{m}{\gcd(m,n)}n.

Minimal requirements

To complete this project, you must be familiar with the built-int types, integer arithmetic including the remainder operator (%) and while loops.

Projects

The possible projects include:

1. Project a. Using the Euclidean algorithm.
2. Project b. Using the binary gcd algorithm.
3. Project c. Using Dijstra's algorithm for the gcd.
4. Project d. Calculating the gcd and lcm of $n$ integers using a recursive algorithm.
5. Project e. Calculating the gcd and lcm of $n$ integers by inspecting the prime factorization of each integer.

Optimizations

1. Optimization i. Minimizing the run-time by sorting the integers in Projects d and e.

Extra stuff...

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;
}