Prime ruby

While watching the MLB playoffs yesterday, I could overhear my wife helping our son with his homework – fractions.  She explained “making the bottom number the same” in terms that he could understand, but I couldn’t help ruminating on the algorithm for computing Least Common Denominator using prime factors.

Then it occurred to me that before you can factor anything, you need access to the set of prime numbers.  Because that set is infinite, this seemed like the perfect application for a continuation-based generator, as outlined in The Ruby Way, by Hal Fulton.

I adapted Hal’s algorithm into a set of class methods, because I wanted to be able to say:

Prime[n] => m

where m is the nth prime.  Because of this random access to prime numbers, I memoized all previously computed primes in an array.

UPDATE 2009-10-13: I streamlined the algorithm for computing the next prime by breaking out of the loop when the next prime to test as a factor is greater than the square root of the candidate prime.

How about determining whether a number is prime?  I reopened Integer and added a prime? method that asks the Prime class about that, by calling Prime.ordinal(n).

I also added an is_factor method to Integer in preparation for computing factors.  You might think that this was as simple as self % factor == 0, but testing revealed that I needed to add tests for zero also.  Then I was able to add:

Prime.factors(n) => ary

where ary is an array of the prime factors of n.

Now that I had prime factorization, I was ready for LCD and GCF.  Implementing those functions, I realized that the array methods | (union) and & (intersection) assume set rules – i.e., they both eliminate duplicates from the original lists.  That won’t work for my purposes, because to compute, for instance, the LCD of 20 and 30, we need the non-uniqued union of their factor lists:  {2, 2, 5} | {2, 3, 5} => {2, 2, 3, 5}, but array union yields [2, 3, 5].  Likewise for GCF we need a non-uniqued intersection.  So I added two methods to Array:  union_dups and intersect_dups.  Each of these methods uses the uniqued version of the respective operation, counts how many of each occur in each array, and puts the max or min (respectively) of that number in the resulting array.

I find it hard to believe that Ruby arrays don’t already have some easier way to do this.  To implement it, I also had to add a how_many method (similar to Lisp’s count-if).  Am I reinventing the wheel here?  Or is this just a “prime” example of how young Ruby still is?