Prime numbers in Common Lisp

As an exercise in my spare time, I decided to translate my Ruby prime number generator to Common Lisp.  What — isn’t that the sort of thing you do in your spare time?

Common Lisp does not have call/cc (that’s a Scheme thing), although it’s possible to implement it.  But in this generator, I really only need one piece of state information:  the list of known primes, from which I can derive the highest known prime and the next number to test.  So I just created a lexical closure for that list, which is shared by the functions that need it.

Other than the use of continuations, the algorithm follows pretty closely the one I developed for Ruby.  I “prime” the list with (2 3) and then test every odd number thereafter.  If the number does not have a factor within the list of known primes from 2 up to the square root of the number itself (inclusive), then it must be prime.  That works because the list of known primes is kept in order from lowest to highest, so once we exceed the square root of our number, it can’t be a factor without the number also having a lower factor.

Given our prime number generator, we can then expose the following functions:

nth-prime n => prime
primep n => n OR nil
prime-factors n => list
lcd &rest integers+ => integer
gcf &rest integers+ => integer

Of course, Common Lisp already implements the last two as lcm and gcd – but they made for a good exercise in mapping lists.  I found through experimentation that, at least in CLISP, union and intersection may or may not remove duplicates from the original lists – it seems to depend on which list comes first.  So I force uniqueness by calling remove-duplicates, then use a method similar to my Ruby implementation to generate the max or min occurrences of each factor.  Rather than creating a new list of the non-uniqued union or intersection, however, I just exponentiate each factor by the appropriate number of occurrences.

The final test in test_prime.lisp is to compute the 10000th prime number.  This takes about 10 seconds on my system.  The same test in my Ruby implementation takes about 4 seconds.  I’m uncertain how much of that difference to attribute to some flaw in my Lisp implementation, the lack of continuations, or an inherent performance difference between the language implementations.  Any improvements on my algorithm will be welcomed.