「ClojureでNinety-Nine Lisp Problems(P34～36)」ブログ用

p34.clj

(declare my-coprime? my-gcd)

(defn my-totient-phi
  "Calculate Euler's totient function phi(m)."
  [m]
  (count (filter #(my-coprime? m %) (range 1 m))))

(defn my-coprime?
  "Determine whether two positive integer numbers are coprime."
  [n m]
  (let [g (my-gcd n m)] (or (== g 1) (== g -1))))

(defn my-gcd
  "Determine the greatest common divisor of two positive integer numbers."
  [n m]
  (cond
    (== n 0) m
    (neg? n) (my-gcd (- n) m)
    (neg? m) (- (my-gcd n (- m)))
    :else (my-gcd (rem m n) n)))

p35-1.clj

(defn my-prime-factors
  "Determine the prime factors of a given positive integer."
  [n]
  (loop [n n, m 2, ps nil]
    (if (> (Math/pow m 2) n)
      (reverse (cons n ps))
      (let [q (quot n m), r (rem n m)]
        (if (== r 0)
          (recur q m (cons m ps))
          (recur n (if (== m 2) (+ m 1) (+ m 2)) ps))))))

p35-2.clj

(declare count-quot)

(defn my-prime-factors
  "Determine the prime factors of a given positive integer."
  [n]
  (loop [n n, m 2, ps nil]
    (if (> (Math/pow m 2) n)
      (let [ps' (if (== n 1) ps (cons n ps))]
        (reverse ps'))
      (let [[q cnt] (count-quot n m),
            m' (if (== m 2) (+ m 1) (+ m 2)),
            ps' (if (== cnt 0) ps (into ps (repeat cnt m)))]
        (recur q m' ps')))))

(defn count-quot
  [n m]
  (loop [n n, m m, cnt 0]
    (let [q (quot n m), r (rem n m)]
      (if (== r 0)
        (recur q m (inc cnt))
        (list n cnt)))))

p36.clj

(declare count-quot)

(defn my-prime-factors-mult
  "Determine the prime factors of a given positive integer (2)."
  [n]
  (loop [n n, m 2, ps nil]
    (if (> (Math/pow m 2) n)
      (let [ps' (if (== n 1) ps (cons (list n 1) ps))]
        (reverse ps'))
      (let [[q cnt] (count-quot n m),
            m' (if (== m 2) (+ m 1) (+ m 2)),
            ps' (if (== cnt 0) ps (cons (list m cnt) ps))]
        (recur q m' ps')))))

(defn count-quot
  [n m]
  (loop [n n, m m, cnt 0]
    (let [q (quot n m), r (rem n m)]
      (if (== r 0)
        (recur q m (inc cnt))
        (list n cnt)))))