The Problem:
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20
My Solution (in C++):
// Author: Will Clausen
//
// Date: Jan 7, 2013
//
// This program will solve Problem 5 from Project Euler.
// I had previously written a solution to this problem in
// python, but it is not fast enough (primarily becuase I
// did not think cleverly about the problem).
#include <iostream>
#include <cstddef>
using namespace std;
size_t gcd(size_t a, size_t b);
size_t lcm(size_t a, size_t b);
size_t problem5(size_t maxDivisor)
{
size_t LCM = 1;
for (size_t i = 1; i <= maxDivisor; ++i) {
LCM = lcm(LCM, i);
}
return LCM;
}
size_t gcd(size_t a, size_t b)
{
if (b == 0)
return a;
if (b <= a)
return gcd(b, a%b);
else
return gcd(b, a);
}
size_t lcm(size_t a, size_t b)
{
return (a*b/gcd(a,b));
}
// Output with maxDivisor 20: 232792560