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

p37.clj

(declare my-prime-factors-mult count-quot)

(defn my-totient-phi-improved
  "Calculate Euler's totient function phi(m) (improved)."
  [m]
  (reduce * (map (fn [[p m]] (* (dec p) (Math/pow p (dec m)))) (my-prime-factors-mult m))))

(defn my-prime-factors-mult
  "Determine the prime factors of a given positive integer (2)."
  [n]
  (loop [n n, [m & ms] (cons 2 (iterate #(+ 2 %) 3)), 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),
            ps' (if (== cnt 0) ps (cons (list m cnt) ps))]
        (recur q ms 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)))))

p38.clj

(declare my-totient-phi my-coprime? my-gcd my-totient-phi-improved my-prime-factors-mult count-quot)

(defn my-measure-phi
  "Compare the two methods of calculating Euler's totient function."
  [m]
  (dorun (map #(time (% m)) (list my-totient-phi my-totient-phi-improved))))

(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)))

(defn my-totient-phi-improved
  "Calculate Euler's totient function phi(m) (improved)."
  [m]
  (reduce * (map (fn [[p m]] (* (dec p) (Math/pow p (dec m)))) (my-prime-factors-mult m))))

(defn my-prime-factors-mult
  "Determine the prime factors of a given positive integer (2)."
  [n]
  (loop [n n, [m & ms] (cons 2 (iterate #(+ 2 %) 3)), 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),
            ps' (if (== cnt 0) ps (cons (list m cnt) ps))]
        (recur q ms 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)))))

p39.clj

(declare my-primes)

(defn my-primes-range
  "A list of prime numbers."
  [n m]
  (reverse (take-while #(<= n %) (my-primes m))))

(defn my-primes
  [n]
  (loop [n n, [m & ms] (cons 2 (iterate #(+ 2 %) 3)), ps nil]
    (if (> m n)
      ps
      (let [ps' (drop-while #(> (Math/pow % 2) m) ps),
            ps'' (if (every? #(not= (rem m %) 0) ps') (cons m ps) ps)]
        (recur n ms ps'')))))