Projects

Project Euler #5

Problem 5 asks: “What is the smallest number divisible by each of the numbers 1 to 20?” Instead of 20, we will consider the question for any natural number.

This is a great question as it gets you to start thinking about number theory! Specifically, how numbers are composed as the products of primes. As an example, 100 can be written as a prime decomposition this way: 2^2*5^2. In fact, all the naturals can be thought of in the form n = p1^a * p2^b * … and so on. So we can think of 1 to 20 as 1, 2, 3, 2^2, 5, 2*3, 7, 2^3, 3^3, …, 2^2*5. Back to the “smallest number divisible by each” part. Obviously, multiplying all the numbers together as has all the numbers as factors, but it isn’t the least common multiple (LCM) of the numbers. This is because some of the base primes are repeated. Consider the set 1 to 5. 1*2*3*2^2*5 = 120, but 60 is also evenly divisible by all the numbers. Since the largest exponent prime, 2^2, already contains the lower exponent prime bases, we only need to collect each prime with the largest exponent found. We can easily compute the largest exponent of each prime by calculating the logarithm of 20 in the base of each prime.

That said, the algorithm is straightforward. First, find the first n primes (20 in this case). I like the Sieve of Eratosthenes, but I adapted Euler’s Sieve for efficiency. Next, for each prime calculate floor(log_prime(20)) and store the prime raised to the result in a variable, product-wise.

Here’s my code and results via codepad.org: http://codepad.org/OYSI1OdF

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s