In an effort to improve my algorithm design I have been working through some of the problems in the Euler Project and have found some of them to be quite intriguing.
Q: What is the largest prime factor of the number 600851475143 ?
I had the following issues to ponder:
- How to store and manipulate a 40-bit unsigned integer?
- To utilize recursion or not?
- Will the algorithm run in less than a minute?
- If not, how do I make it more efficient?
The end result was simpler and much more performant than I had expected. The 40-bit input fit into a long just fine. Recursion was not necessary, and average runtimes are in the single digit millisecond range. There was even an opportunity to use some very basic LINQ to retrieve the largest factor from the List
Here is the C# code:
using System;
using System.Collections;
using System.Collections.Specialized;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;
namespace Euler3
{
class PrimeFactorization
{
const long ToFactor = 600851475143;
public static List<long> theFactors = new List<long>();
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
sw.Reset();
sw.Start();
Console.WriteLine("Highest prime factor of (" + ToFactor + ") is " + HighestPrimeFactor(ToFactor));
sw.Stop();
Console.WriteLine("Factorization algorithm runtime was: " + sw.ElapsedTicks + " ticks or " + sw.ElapsedMilliseconds + "ms");
Console.ReadLine();
}
private static long HighestPrimeFactor(long input)
{
bool searching = true;
long highestFactor = 0;
while (searching)
{
long factor = IsPrime(input);
if (factor != -1)
{
theFactors.Add(factor);
input = input / factor;
}
if (factor == -1)
{
theFactors.Add(input);
highestFactor = theFactors.Max();
searching = false;
}
}
return highestFactor;
}
private static long IsPrime(long input)
{
if ((input % 2) == 0)
{
return 2;
}
else if ((input == 1))
{
return 1;
}
else
{
long threshold = (Convert.ToInt64(Math.Sqrt(input)));
long tryDivide = 3;
while (tryDivide < threshold)
{
if ((input % tryDivide) == 0)
{
Console.WriteLine("Found a factor: " + tryDivide);
return tryDivide;
}
tryDivide += 2;
}
Console.WriteLine("Found a factor: " + input);
return -1;
}
}
}
}Output:
-Surely a blog entry title such as this earns me some sort of special place in Geek Hell.