Finding prime factors of a number

Okay, so just having a little fun I thought I'd see if I could write an algorithm to find all of the prime factors of a number. The solution I came up with is as follows:

class Program
{
    static void Main(string[] args)
    {
        var subject = long.MaxValue;
        var factors = new List();
        var maxFactor = 0;

        Console.WriteLine("Factoring {0} ...", subject);

        var sw = new Stopwatch();
        sw.Start();

        while (subject > 1)
        {
            var nextFactor = 2;
            if (subject % nextFactor > 0)
            {
                nextFactor = 3;
                do
                {
                    if (subject % nextFactor == 0)
                    {
                        break;
                    }

                    nextFactor += 2;
                } while (nextFactor  maxFactor)
            {
                maxFactor = nextFactor;
            }
        }

        sw.Stop();

        var factorAnswer = 1L;
        factors.ForEach(f => factorAnswer *= f);

        Console.WriteLine("Factors: {0} = {1}",
            string.Join(" * ",
                factors.Select(i => i.ToString()).ToArray()),
            factorAnswer);
        Console.WriteLine("Max Factor: {0}", maxFactor);
        Console.WriteLine("Elapsed Time: {0}ms", sw.ElapsedMilliseconds);
    }
}

and its output is:

Factoring 9223372036854775807 ...
Factors: 7 * 7 * 73 * 127 * 337 * 92737 * 649657 = 9223372036854775807
Max Factor: 649657
Elapsed Time: 3ms

It works, and IMO awfully fast, but it's a little brute force. Is there a better way of doing it?

Other algorithms

Wikipedia has an article which lists other Factoring algorithms.

Your algorithm

Re. your algorithm, I see you're checking all odd numbers, which includes non-prime numbers such as 9.

Your sieve would be faster if you only checked prime numbers, for example by using a list like this one or this one.

Furthermore you're checking all the way to subject. Your last time through the loop would be faster if you give up as soon as nextFactor > sqrt(subject).

Your C# code

As for your C# code:

• What type is nextFactor when you declare it as var nextFactor = 2;? I fear that it might be int not long.

• Your code might be very slightly faster if you used the Capacity property of List.

• There's something very strange (and slow) about your loop: after you find a nextFactor value such as 7, then you begin your search from 2 again! You code would be faster if you moved your long nextFactor = 2; initialization to do it only once, before/outside the while loop, and changed your nextFactor = 3; statement to nextFactor += (nextFactor == 2) ? 1 : 2;. You could then also eliminate your maxFactor variable, because the largest factor value would be left/stored in nextValue after you exit the while loop.

• It might be better to use System.Numerics.BigInteger instead of long (because long.MaxValue is only about 10^18, whereas some people want to factorize larger numbers than that).

StackExchange Code Review Q#40572, answer score: 12