99 Clojure Problems (31-34)
I wanted to complete problems 27 and 28, but it just wasn’t working out. I’ll come back to them later, but for now, here’s numbers 31 through 34.
Since I’m working through Project Euler as a sort of algorithmic kata to stretch my legs in new languages, these prime based problems were a snap.
; A utility method that helps keep things readable. (defn evenly-divisible [n d] (zero? (mod n d))) ; P31 (**) Determine whether a given integer number is prime. (defn prime? [n] (loop 1 (if (> (* c c) n) true (if (evenly-divisible n c) false (recur (inc c)))))) ; P32 (**) Determine the greatest common divisor of two positive integer numbers. (comment "Use Euclid's algorithm.") ; my first attempt... (defn gcd_a [n k] (loop [a (if (< n k) n k) b (if (< n k) k n) c 2 o 1] (cond (< a c) o (and (evenly-divisible a c) (evenly-divisible b c)) (recur (/ a c) (/ b c) c (* o c)) :else (recur a b (inc c) o)))) (comment "using euclid's algorithm, which I thought I knew, but I was apparently misremembering") (defn gcd [m n] (if (zero? n) m (recur n (mod m n)))) ; P33 (*) Determine whether two positive integer numbers are coprime. (comment "Two numbers are coprime if their greatest common divisor equals 1.") (defn coprime? [n k] (= 1 (gcd n k))) ; P34 (**) Calculate Euler's totient function phi(m). (comment "Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r <= m) that are coprime to m.") (defn totient [n] (count (filter (fn [e] (coprime? e n)) (range 1 n))))
Not only was Project Euler helpful, the fact that these solutions so nicely build upon each other helped speed these through. I think I made the right choice skipping 27-28. The forward momentum has rekindled my interest in learning more about clojure.