Will Clausen's Website

Categories
WCW

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

Leave a Reply

Your email address will not be published. Required fields are marked *