I'm sure you can do better than a linear search in primes_up_to(). I'd start with a binary search, I think, since you've got an ordered set. You could also play with caching past searches and use that to pick a subset to search - depending on usage patterns that could be a big win.

-sam