Wow that's a big integer! What's its largest prime factor? I see that there are a few other people who have tackled Project Euler Problem #3. I hope you're not all sick of that question yet. I've not taken a look at those yet (purposely), but am about to now. 

I feel like I did a pretty good job on this one, but you tell me. How can I further improve this code? I'm particularly interested in how it could be made even faster, but it seems to already be a pretty quick implementation. My first version took over an hour, this one runs almost instantly. I'm also interested in how I could have used a List&lt;T&gt; instead of an array, if you feel that would have been a better data structure.


  The prime factors of 13195 are 5, 7, 13 and 29.
  
  What is the largest prime factor of the number 600851475143 ?


Numbers.cs - 79 Lines

There are three functions: IsPrime, IsFactor, and PrimeFactors. 

namespace Challenges
{
    public class Numbers
    {
        public static Boolean IsPrime(Int64 number)
        {
            if (number &lt; 2)
            {
                return false;
            }

            if (number == 2)
            {
                return true;
            }

            if (number % 2 == 0)
            {
                return false;
            }

            double sqrtOfNumber = Math.Sqrt(number);

            for (var index = 3; index &lt;= sqrtOfNumber; index += 2) //skip even numbers 
            {
                if (number % index == 0)
                {
                    return false;
                }
            }

            return true;

        }

        public static bool IsFactor(Int64 dividend, Int64 divisor)
        {
            return (dividend % divisor == 0);
        }

        public static Int64[] PrimeFactors(Int64 number)
        {
            Int64[] results = { };

            Int64 maxDivisor = number / 2;
            int index = 0;
            for (Int64 divisor = 2; divisor &lt; maxDivisor; divisor++ )
            {
                if (IsFactor(number,divisor) &amp;&amp; IsPrime(divisor))
                {
                    Array.Resize(ref results, results.Length + 1);
                    results[index] = divisor;
                    index++;

                    Int64 factor = number / divisor;
                    if (IsPrime(factor))
                    {
                        Array.Resize(ref results, results.Length + 1);
                        results[index] = factor;
                        break;
                    }
                    else
                    {
                        Int64[] recursiveResults = PrimeFactors(factor);
                        Array.Resize(ref results, results.Length + recursiveResults.Length);
                        for (int i = 0; i &lt; recursiveResults.Length; i++)
                        {
                            results[index] = recursiveResults[i];
                            index++;
                        }
                        break;
                    }
                }
            }

            return results;
        }
    }
}


Console Program

To prove it works, you can check my answer.

namespace Challenges
{
    class ProjectEuler3Program
    {
        static void Main(string[] args)
        {
            const Int64 verybigint = 600851475143;
            Int64[] factors = Numbers.PrimeFactors(verybigint);

            Console.WriteLine((factors.Max()));

            Console.WriteLine();
            Console.WriteLine("Press enter to close...");
            Console.ReadLine();
        }
    }
}
What a fascinating solution!  It seems that for every smart decision you made, you also threw in a poor decision or two.

Smart decision: In PrimeFactors(), you start testing divisors from small to large, rather than large to small.

Poor decision: You used if (IsFactor(number,divisor) … rather than while (IsFactor(number,divisor)).  Using if instead of while disastrously complicates the program.

Smart decision: In IsPrime(), the index loop skips even numbers.  (Why is the variable named index?)

Poor decision: The divisor loop in PrimeFactors() doesn't skip even numbers.

Smart decision: In IsPrime() the index loop goes up to Math.Sqrt(number).

Poor decision: In PrimeFactors(), the divisor loop goes all the way up to number / 2.

Smart decision: You defined an IsFactor() function for readability, and used it in PrimeFactors().

Poor decision: You didn't use IsFactor() in IsPrime().

Smart decision: In PrimeFactors(), whenever you find a successful divisor, you continue the calculation based on factor = number / divisor rather than number.

Poor decision: You continue to factor factor by recursion instead of looping.  Worse, the way you used recursion requires you to append the results to the results array.

Poor decision: In the innermost if-else of PrimeFactors()…

if (IsPrime(factor))
{
    …
} else {
    Int64[] recursiveResults = PrimeFactors(factor);
    …
}


the call to PrimeFactors() repeats a lot of throwaway work that was done by IsPrime().

Overall, though, the fundamental issue is the if-vs.-while distinction.  Had you chosen while, then you could…


enumerate the successful divisors in nondecreasing order.  Currently, you keep a list of all prime factors and find its maximum.  If you could obtain the divisors in order, then you wouldn't need to bother with keeping a list at all.
eliminate IsPrime() altogether.  Every successful divisor will necessarily be prime since you will have factored out all smaller divisors already.