### Clojure Golf – Episode 2: Largest Prime Factor

In the last episode of Clojure Golf we saw some interesting ways to write a function that takes a couple sequences, applies a function to the pairing elements, and then returns a list of the results based on a supplied filtering function. Thanks to all who participated in that exercise.

This episode is a little tougher.

Below I have written a function that takes two numbers: any given number, and another number that acts as a starting point. This function will then calculate the largest prime factor of the given number. The implementation of this function came from a Twitter meme where people would describe songs in code within the constraints of 140 characters. As it turns out, *most* of the snippets were meant to be humerous and didn’t actually run or represent legal source programs at all. I wanted to break that trend while still maintaining some sense of humor about the whole thing. In any case, before I thought of an entry I knew that my snippet would deal with the Tommy Tutone song 867-5309/Jenny. However, what I didn’t know at the time was that the number 8675309 is a prime number ^{1}, but once I realized this I knew what my #songsincode entry would be.

[sourcecode lang=”clj” gist=”183954″] ;; largest prime factor (defn lpf “Takes a number n and a starting number d > 1 and calculates the largest prime factor of n starting at number d.

usage: (lpf 364362978 2) => 8675309″ [n d] (if (> d n) (- d 1) (recur (#(if (zero? (rem % d)) (recur (/ % d)) %) n) (inc d)))) [/sourcecode]

I think the above function is likely as small as it can get ^{2}, but it’s not very fast (e.g. `(lpf 1234567890123456789012345678901234567890 2)`

^{3} took about 10 minutes on my machine). Therefore, this episode of Clojure Golf is devoted to making `lpf`

as fast as possible, while still preserving as much compactness as possible. It would also be nice to see how to squeeze a few more characters out of this particular implementation.

As always, Clojure snippets are not required — any programming language is encouraged.

-m

## One Comment, Comment or Ping

Tracy Harms

In the J programming language, the following takes about two-tenths of a second to run on my aging laptop:

`{:q: 1234567890123456789012345678901234567890x 5964848081`

We may define lpf as a named function if we wish.

`lpf=: [: {: q:`

Sep 9th, 2009

## Reply to “Clojure Golf – Episode 2: Largest Prime Factor”