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?