Problem description, from Project Euler

What is the largest prime factor of the number N?

Solution

In previous problems, I was using a list of primes I got somewhere else. I figured it would be relevant to implement a prime-finding algorithm. I decided to go with simplicity, and implement the Sieve of Eratosthenes. It’s basically the algorithm you would come up with yourself if you wanted to figure out how to find all the prime numbers within a certain range.

Say we want to find all the prime numbers between 1 and 100. Start with the first prime number 2. Remove from the list all multiples of 2. Work with the next prime number 3. Remove from the list all multiples of 3. Continue until the square number you pick is greater than the last number in the list. This is because no number after that will have a multiple in the list.

For the part where we factor primes, I used the algorithm I came up with for problem 5, even though it is inelegant and has a kludgy fix.

Overall, I was happy with my solution. I think I am beginning to think more “functionally.”

; flattens a nested list
(defn flatten [x] (let [s? #(instance? clojure.lang.Sequential %)] (filter (complement s?) (tree-seq s? seq x))))

; //en.wikipedia.org/wiki/Sieve_of_Eratosthenes
(defn sieve-of-eratosthenes
    [n]
    (defn sieve-of-eratosthenes-helper
        [n]
        ; step 1 Create a list of consecutive integers from two to n: (2, 3, 4, ..., n),

    (defn sieve [rng p]
        (
            ; this lambda used to perform the actual recursion
            (fn [new-rng]
                ; step #5 Repeat steps 3 and 4 until p^2 is greater than n.
                (if (<= (* p p) n)
                    ; recurse
                    (sieve new-rng
                        ; step # 4 Find the first number remaining on the list after p
                        ; (it's the next prime); let p equal this number,
                        (first (filter #(> % p) new-rng))
                        )
                    ; end recursion otherwise
                    new-rng
                    )
                )
            ; this is an argument to the lambda above
            ; step #3 While enumerating all multiples of p starting from p2,
            ; strike them off from the original list,
            (filter
                #(or
                    (not= ; divisible by p
                        (rem % p)
                        0
                        )
                    ; greater than p^2
                    (< % (* p p))
                    )
                    rng
                )
            )
        )

    (sieve
        (range 2 n)
        2 ; step #2 Initially, let p equal 2, the first prime number
        )
    )

(sieve-of-eratosthenes-helper n)
)


(defn problem03 [n]
    ; begin by generating primes below the sqrt of the number.
    ; I'm just guessing this will be good enough. I started
    ; with a guess of 1000, which was woefully small
    (def prime-cache (sieve-of-eratosthenes (. java.lang.Math (sqrt n))))
    (defn prime?
        [n]
        (not (nil? (some #(= n %) prime-cache)))
        )
    ; prime-factorization algorithm from solving previous
    ; project Euler problems such as #5
    (defn prime-factorization
        [n]
        (defn pf-helper
            []
            (def first-divisible
                (first (filter
                    #(zero?
                        (rem n %)
                        )
                    (rest prime-cache))
                    )
                )

        (def result (/ n first-divisible))

        (def new-result
            (if (not (prime? result))
                (prime-factorization result)
                [result]
                )
            )

        ; i don't know why I need to set this again.
        ; the recursion seems to mutate a value that
        ; should not be in its scope
        (def first-divisible
            (first (filter
                #(zero?
                    (rem n %)
                    )
                (rest prime-cache))
                )
            )

        (if (nil? new-result)
            nil
            (if (nil? first-divisible)
                [new-result]
                (flatten [new-result first-divisible])
                )
            )
        )

    (if (prime? n)
        [n]
        (pf-helper)
        )
    )

; factor!
(prime-factorization n)

)