Click here to Skip to main content
Click here to Skip to main content

Project Euler Problem #5

, 11 Aug 2011
Rate this:
Please Sign up or sign in to vote.
Project Euler Problem #5

Ready or not, here comes problem five!

2520 is the smallest number that can be divided by each of the numbers 
from 1 to 10 without any remainder. 

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

This one really doesn't require that much explanation. I suppose we could easily brute force this one also, but that just isn't my style. So I'll just go ahead and show the final return statement that gives us the answer:

 return Enumerable.Range(1, 20).Aggregate(this.LeastCommonDivisor);

....Alright....that's it. Let's go home.

No?

Okay fine. Let me explain a bit. We are using the 'Aggregate' Extension here on our range of 1-20. The 'Aggregate' method will take our recursive method 'LeastCommonDivisor'.

Here is that function:

 private int LeastCommonDivisor(int i, int j)
 {
 	return (i == 0) || (j == 0) ? 0 : (i / this.GreatestCommonDivisor(i, j)) * j;
 }

That function also makes reference to this function to recursively find the greatest common divisor:

 private int GreatestCommonDivisor(int i, int j)
 {
 	return (j == 0) ? i : this.GreatestCommonDivisor(j, i % j);
 }

Now our 'Aggregate' method will calculate the smallest positive number that is evenly divisible by all of the numbers from 1 to 20.

This problem was not that enjoyable to me, but oh well. I found some great references by Basildon Coder and Functional Fun. From these guys, I was able to figure something out. Anyways, here it is. Do with it what you will.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Jared Wallace
Business Analyst
United States United States
Visit my blog, Aimless Technical Babble

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Mobile
Web01 | 2.8.140721.1 | Last Updated 11 Aug 2011
Article Copyright 2011 by Jared Wallace
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid