© 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;
int main () {
unsigned long sumsquares = 0, sums = 0;
int n;
cout <> n;
while (n < 0) {
cout <> n;
}
for(int i = 1; i <= n; i++) {
cout << "i: " << i << endl;
sumsquares += i * i;
cout << "sumsquares: " << sumsquares << endl;
sums += i;
cout << "sums: " << sums << endl;
}
cout << "The sum of squares from 1 to " << n << ": " << sumsquares << endl;
cout << "The square of sums from 1 to " << n << ": " << sums * sums << endl << endl;
cout << "The difference: " << (sums * sums - sumsquares) << 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).