## Project Euler 003 – C#

15 02 2011

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Solution

using System.Collections.Generic;

using System;

namespace ProjectEulerCSharp_002

{

class Program

{

static void Main(string[] args)

{

List<long> factors = PrimeFactor(600851475143);

// this sorts the numbers in ascending order

factors.Sort();

// this reverses the list so the biggest one

// is on top.

factors.Reverse();

//show me the money

System.Console.WriteLine(factors[0]);

}

public static List<long> PrimeFactor(long number)

{

//here is our list of prime factors

List<long> factors = new List<long>();

//assume the number is prime

//unless we find a factor

bool isPrime = true;

//here is the upper limit of what we need to test

long factorCandidate = (long)Math.Sqrt(number);

while (factorCandidate > 1)

{

//is this a factor?

if (number % factorCandidate == 0)

{

//if so, what are it’s factors?

PrimeFactor(factorCandidate));

PrimeFactor(number / factorCandidate));

//we know this one isn’t prime

isPrime = false;

}

//next

factorCandidate–;

}

//we are only adding prime factors

//send ’em back

return factors;

}

}

}

Discussion

In contrast to my F# solution this didn’t take much longer than 5 minutes to write.  I didn’t spend any time optimizing it because it ran so fast for the problem already.

## Project Euler 002 – C#

8 02 2011

Problem 2

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution

namespace ProjectEulerCSharp_002

{

//By considering the terms in the Fibonacci sequence

//whose values do not exceed four million, find the

//sum of the even valued terms.

class Program

{

static void Main(string[] args)

{

//typically when calculating fibonacci series

//it’s performed two elements at a time

//this is not a requirement

int fib0 = 1;

int fib1 = 1;

int fib2 = 2;

while (fib2 < 4000000)

{

//we know the fib2

//is always even

//and represents ALL

//evens in the series

//see the ‘proof’ below

//odd + even = odd

fib0 = fib1 + fib2;

//odd + even = odd

fib1 = fib0 + fib2;

//odd + odd = even

fib2 = fib0 + fib1;

}

}

}

}

Discussion

As I mentioned in the F# solution, an obvious optimization is to sum as you go.  I’ve also taken it a step further and removed the check for evenness because every third Fibonacci is even.  I layout a rough proof in my comments above.

## Project Euler 001 – C#

1 02 2011

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Solution

namespace ProjectEulerCSharp_001

{

//Add all the natural numbers below one

//thousand that are multiples of 3 or 5.

//first, we will get all of

//the numbers divisible by 3

class Program

{

static void Main(string[] args)

{

// add the 3’s, the 5’s, and subtract one set of 15’s

for (int three = 0; three < 1000; three += 3)

for (int five = 0; five < 1000; five += 5)

for (int fifteen = 0; fifteen < 1000; fifteen += 15)

}

}

}

Discussion

If you saw the F# solution then this should be a relatively easy translation.  The main difference is that I create the sum as I’m building the list.