User Tools

Site Tools


This is an old revision of the document!

Prime Numbers

Difficulty: Medium

Topics: primes

* Write a function which returns the first x number of prime numbers.

(= (__ 2) [2 3])

(= (__ 5) [2 3 5 7 11])

(= (last (__ 100)) 541)


(fn pys [n]
    (take n ((fn sieve [s]
  (cons (first s)
        (lazy-seq (sieve (filter #(not= 0 (mod % (first s)))
                                 (rest s)))))) (iterate inc 2))))

maximental's solution:

(comp (partial apply take) reverse list)
(remove (comp (partial apply some)
              (juxt (partial partial (comp zero? rem))
                    (partial range 2))) 
        (iterate inc 2))

(fn [n]
  (take n
    (remove (fn [k] (some #(zero? (rem k %)) 
                           (range 2 k)))
            (iterate inc 2))))

psk810's solution:

(fn [n]
  (loop [primes [] nums (iterate inc 2)]
    (if (= n (count primes))
        (recur (conj primes (first nums)) 
               (filter #(not= 0 (mod % (first nums))) nums)))))

Greatest Common Divisor

Difficulty: Easy


Given two integers, write a function which returns the greatest common divisor.

(= (__ 2 4) 2)

(= (__ 10 5) 5)

(= (__ 5 7) 1)

(= (__ 1023 858) 33)

maximental's solution:

(fn g [a b] (if (= b 0) a (g b (rem a b))))

psk810's solution:

(fn [x y]
  (let [a (max x y) b (min x y) r (rem a b)]
    (loop [a a b b r r]
      (if (zero? r)
          (recur b r (rem b r))))))

cf. lcm

(fn lcm
  [a b]
  (when (or (not (integer? a)) (not (integer? b)))
    (throw (IllegalArgumentException. "lcm requires two integers")))
  (cond (zero? a) 0
        (zero? b) 0
        :else (* b (quot a ((fn gcd
  [a b]
   (= a b) a
   (> a b) (recur (- a b) b)
   :else   (recur (- b a) a))) a b)))))

cf. mod

(defn mod
  "Modulus of num and div. Truncates toward negative infinity."
  {:added "1.0"}
  [num div] 
  (let [m (rem num div)] 
    (if (or (zero? m) (pos? (* num div))) 
      (+ m div))))
lecture/4clojure/prime_numbers_67번_문제_풀이.1365484023.txt.gz · Last modified: 2019/02/04 14:26 (external edit)