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 ?


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


            // this reverses the list so the biggest one

            // is on top.



            //show me the money





        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?



                    //what about the other divisor?


                        PrimeFactor(number / factorCandidate));

                    //we know this one isn’t prime

                    isPrime = false;





            //we are only adding prime factors

            if (isPrime) { factors.Add(number); }

            //send ’em back

            return factors;






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.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (




Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your 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: