Finding prime factors of a number?

Question

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<long>();
        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 < subject);
            }

            subject /= nextFactor;
            factors.Add(nextFactor);
            if (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?

Answer 1

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

Answer 2

Code

Your code seems fine.

Like @ChrisW highlighted, take care about types. Your variables nextFactor and maxFactor are actually integers.

Also, string.Join can take objects - it will call ToString() internally. You can convert string.Join(" * ", factors.Select(i => i.ToString()).ToArray()) to string.Join(" * ", factors)

Algorithm

I suggest 2 improvements to the algorithm.

You are re-iterating values that you already discarded as not being factors.

If 2 is not a factor of subject on the first iteration, it will never be. So when you find a new factor X, on the next iteration you can continue looking for factors from X upwards - instead of re-checking the already-discarded values [2..X].

You only need to check until nextFactor*nextFactor>subject

And then the last factor is actually subject itself. :)
Right now, you check until nextFactor==subject (thus next iteration subject==1).

Explanation:

if subject is e.g. 21 and nextFactor is 11... since no number smaller than 11 is a factor, then all its factors are bigger or equal to 11.

• If subject has one factor, that factor must be the subject itself (21);
• If it has more than one, and because its factors are at least as big as 11, then 21>=X*Y, X>=11, and Y>=11.
  (X being the next factor, and Y being the next subject.)

So, in the case where nextFactor*nextFactor > subject, you know that the last factor has to be subject itself, and you can terminate processing earlier.