© 2024 fjorge. All rights reserved.

# Project Euler Problem 5

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).