The problem: find the largest prime factor of 600851475143.
I used the Sieve of Eratosthenes and Ruby to solve it
This time, I tried a lazy, functional approach. The result was an
efficient, straightfoward solution that involved no sieve or any
static/full-realized data structure at all! I make a recipe for the
kind of numbers I want and then take just as many as I need in order
to finally output the answer.
Here's my lazy, functional implementation using Clojure 1.5 RC1
(mostly because I wanted to play with the new reducers library). It's pretty efficient: less than a quarter of a second on my 2011 13" base
(ns euler.three (require [clojure.core.reducers :as r])) (declare largest-prime-factor-for) (declare factors-of) (declare source-factors) (declare source-naturals) (declare factor?) (declare prime?) (declare certainty) (defn answer  (time (largest-prime-factor-for 600851475143))) (defn largest-prime-factor-for [n] (let [prime-factors (r/filter prime? (factors-of n))] (last (into  prime-factors)))) (defn factors-of [n] (r/filter #(factor? n %) (source-factors n))) (defn source-factors [n] (r/take-while #(< % (int (Math/sqrt n))) (source-naturals))) (defn source-naturals  (r/map #(+ % 2) (range))) (defn factor? [n possib] (zero? (mod n possib))) (defn prime? [n] (.isProbablePrime (BigInteger/valueOf n) certainty)) (def certainty 10)