First I’d like to thank Stefaan for introducing me to Project Euler. Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.
Most of the problems you can brute force in resonable time, but the challenge is more of a personal level in trying to solve them elegant or in as few lines as possible.
I quickly found that the magic of yield return and Linq was well suited to solve several of the problems I’ve encountered yet. So I decided to write a blog post about them and share my new-found knowlege of Linq.
Problem 1: Add all the natural numbers below one thousand that are multiples of 3 or 5
The Enumerable pattern is quite extraordinary when used in Linq like this. So I decided to use the same pattern on other problems as well.
[code lang="csharp"]
return Enumerable.Range(1, 999)
.Where(x => x % 5 == 0 || x % 3 == 0)
.Sum();
[/code]
Problem 2: Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million
First I made a sequence generator for Fibonacci numbers:
[code lang="csharp"]
internal static IEnumerableFibonacciSequence()
{
long last1 = 1;
yield return 1;
long last2 = 2;
yield return 2;
while (true)
{
long next = last1 + last2;
last1 = last2;
last2 = next;
yield return next;
}
}
[/code]
Problem 3: What is the largest prime factor of the number 600851475143 ?
Again I start with creating a sequence generator. This one returns the sequence of factors for any number.
[code lang="csharp"]
internal static IEnumerable GetFactors(long x)
{
for (long factor = 1; factor * factor <= x; factor++)
{
if (x % factor == 0)
{
yield return factor;
if (factor * factor != x)
yield return x / factor;
}
}
}
[/code]
We also need a small helper function to check if a number if a prime number:
[code lang="csharp"]
private static bool IsPrime(long num)
{
long limit = (long)Math.Sqrt(num);
for (long d = 2; d <= limit; d++)
{
if (num % d == 0)
return false;
}
return true;
}
[/code]
Finally the actual Linq query to find the largest prime factor of the number 600851475143 :
[code lang="csharp"]
var primeFactors = from factor in GetFactors(600851475143)
where IsPrime(factor)
select factor;
return primeFactors.Max();
[/code]
I also have use the same pattern on several of the other problems like nr 10: Find the sum of all prime numbers below 2 000 000:
[code lang="csharp"]
return PrimeNumbers()
.TakeWhile(x => x < 2000000)
.Sum();
[/code]
8752 downloads
