Project Euler Problem #5

November 7, 2009

Read the details of the problem here

Summary

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

Solution

I didn’t need to write a program for this question. I vaguely remembered from school that the LCM of a series of numbers is just the product of the maximum powers of its prime factors, or something like that terminology.

It goes something like this. 2^4 = 16, which is less than 20, so that’s included but 2^5 isn’t as 32 is greater than 20. Similarly 3^2 = 9, is in, but 3^3 = 27 is out. Intermediate numbers will always be able to be factored into products of lesser powers of the primes and can therefore be ignored.

So this gives the list: 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19

So it wasn’t really much of a program to be written though groovysh did the calculation admirably. Performance wasn’t an issue!

Conclusion

Just goes to show it’s sometimes worth engaging brain before hitting the keyboard.

Reading ahead in the Project Euler questions it looks like factorization of large numbers is an ongoing theme so I’ll probably end up writing something that does this but I’ll do that when I need it.

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: