Primes and Sieves

Project Euler is one of the best things I have discovered in a while. It’s simply a huge open list of problems in numeric order that you can solve using any math or code you want, provided that any code you write runs under one minute.

The problems get interesting from the very start and are actually entertaining! After reading Lokhart’s Lament, I’d say these problems would definitely fit the category of challenging and yet stimulating. Math truly is an art, and code is a cool way to access a subset of it.

Anyway, primes! Here’s the problem itself:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

And here’s my solution (skip if you want to try this yourself!):

def maxPrimeFactor(n) #=> maxPrimeFactor(600851475143) => 6857 in 2007.562 ms
  # limit the ridiculous range safely
  range = n**(1/Math.sqrt(n.to_s.length).floor.to_f)
  ary = (1..range).to_a
  # Sieve of Eratosthenes (replace with Sieve of Atkin?)
  for i in ary
    for j in ary
      if i != j
        if (j % i == 0)
          ary.delete(j)
        end
      end
    end
  end
  #remove non-factor primes
  ary.delete_if{|k| ( n % k != 0)}
  ary.max
end

The code should be pretty much clear, at least except for that initial part where I restrict the range. It was hard getting my super-easy-to-write-yet-inefficient prime numbered array generator to solve for 600851475143 quickly. I was too lazy to try to implement Sieve of Atkin so I just decided to try limiting the range as much as I could. Apparently, if you take the root of the number of digits in the given composite number, and then raise the upper limit of your range to the inverse of that number, you get a much more limited range that still gives you the right highest prime factor of the original number. I tried this out down to two-digit composites and it seems to work.

Also, if I tried using a quick prime test on each element and deleting non-primes that way (instead of a sieve), the performance was actually worse somehow. And while trying to do this exact thing, I discovered a freaking regular expression that detects primes! Yeah.

I literally spent close to three hours just researching a number of tangential topics, such as Sieve of Eratothenes, Sieve of Atkin, Sieve theory, GNFS, and RSA. While the problem itself wasn’t too challenging (I ended up learning much more about Ruby, though), the whole experience was amazing. And of course, there’s a lot of room for gains in efficiency too.

I highly recommend you sign up for an account on Project Euler and work your way through some of those problems! It’s a great way to try out new languages, learn more efficient techniques, or just have some fun. No, really, it’s actually fun.