## 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.