Project Euler #3

Posted by Robert Green on June 30, 2009 Leave a comment (0) Go to comments

Project Euler #3 is :

Find the largest prime factor of a composite number.

My first attempt at this whipped up some typical code that simply brute forced my way to the solution. My code looked like this:

static void Problem3() {
    long n = 600851475143;
    int factor = 2;
    int lastFactor = 1;
 
 
    if(n % 2 == 0) {
        lastFactor = 2;
        n = n / 2;
        while(n % 2 == 0) {
            n = n / 2;
        }
     } else {
         lastFactor = 1;
     }
     factor = 3;
 
     double maxFactor = Math.Sqrt(n);
     while(n > 1 && factor <= maxFactor) {
          if(n % factor == 0) {
              n = n / factor;
              lastFactor = factor;
              while(n % factor == 0) {
                  n = n / factor;
              }
              maxFactor = Math.Sqrt(n);
          }
          factor += 2;
      }
 
      if(n == 1) {
          Console.Write(lastFactor.ToString() + " ");
      } else {
          Console.Write(n.ToString() + " ");
      }
}

Not very elegant, but it works. So I set out to find something a bit prettier and I came across I LINQ solution here. All I did was tack on the .AsParallel() in order to give it a little speed boost. The code looks like:

static void LinqProblem3() {
    long largeNumber = 600851475143;
    var allPrimeFactors = from p in Primes.PrimeFactors(largeNumber).AsParallel()
                                 orderby p descending
                                 select p;
 
    foreach(var f in allPrimeFactors){
        Console.WriteLine(f);
    }
}
 
public static class Primes {
 
    // Find all prime factors.
    public static IEnumerable<int> PrimeFactors(long number) {
        // Start by removing the lowest prime (2)
        return MorePrimeFactors(number, 2);
    }
 
    // This recursive method finds all prime factors.
    private static IEnumerable<int> MorePrimeFactors(long number, int factor) {
        // Find the next prime factor
	while(number % factor != 0)
	    factor++;
	// Return it.
	yield return factor;
 
	// look again...
	if(number > factor)
		// recursively look for this factor again, using Num/factor
		// as the new big number
		foreach(int factors in MorePrimeFactors(number / factor, factor))
			yield return factors;
	}
}