I’ve been having some fun doing the first few problems of Project Euler and figured I’d share my solution to problem 5 here.

The Problem
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

The Solution
This problem, worded another way, asks what the least common multiple of all the integers between 1 and 20 is. Since multiplication is commutative, the least common multiple of a series is the same as computing the least common multiple of all the numbers before it and the current. So, LCM(1…6) is the same as LCM(6, LCM(5, LCM(4, LCM(3, LCM(2, 1))))).

#include 
using namespace std;

unsigned long gcd(unsigned long a, unsigned long b) {
	if(b == 0)
		return a;
	return gcd(b, a%b);
}

unsigned long lcm(unsigned long a, unsigned long b) {
	return a * b / gcd(a,b);
}

int main ()
{
	unsigned long answer = 1;
	for(long i = 1; i <= 20; i++) {
		cout << "i: " << i;
		answer = lcm(answer, i);
		cout << " lcm: " << answer << endl;
	}

	return 0;
}

My solution uses an algorithm to compute the least common multiple that involves finding the greatest common divisor as follows: lcm(a, b) = a*b / gcd(a, b). I used the Euclid method of finding the greatest common divisor: gcd(a,0) = a; gcd(a, b) = gcd(b, a mod b).