Will Clausen's Website


Solution: Project Euler Problem 5

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);
		return gcd(b, a);

size_t lcm(size_t a, size_t b)
	return (a*b/gcd(a,b));

// Output with maxDivisor 20: 232792560

Leave a Reply

Your email address will not be published.