idea log

Project Euler (Problem III)

I did a little analysis of my blog posts from the past month that I've been blogging and it turns out that the Project Euler related content is the most popular and most viewed content on the site. Who would've thought?  I guess the internet is a popular place for mathturbation.

The third Project Euler problem is a prime factorization problem.  There are many, many, many problems on Project Euler which require factoring prime numbers and this is one of the easiest.  Given a very large number we need to find the largest prime factor to submit as our answer.  The solution we use for prime factorization we will be able to reuse later on in a number of other problems.

There are actually many different methods for finding prime factors and it can get complicated quickly.  Check out the various "sieves" and other methods from wikipedia - GNFS, SNFS, Euler, Fermat.  Did you see the Big O notation for the general number field sieve?  I don't know how to parse that - Crazy!

I used trial division.  It is the simplest method of integer factorization.  It's not going to win any RSA contests but it'll work for the Project Euler problems.  Here is the basic trial division algorithm (in C#):

show/hide

Now you just plug in your big number and voila - you've solved the problem. It runs suprisingly fast on my box.

posted @ Monday, March 31, 2008 8:48 AM