≡ Menu

Clojure ProjectEuler No. 3 – Largest Prime Factor

Project Euler 3

Ok, post lagi tentang ProjectEuler, kali ini dengan problem no. 3. Problemnya tidak lain adalah mencari faktor bilangan prima terbesar.

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143?

Ide saya cukup naive:
1. Filter prime dari sqrt 600851475143 down to 4!
2. Lewat bilangan genap!
3. Apply max!

Yang akan saya bahas adalah bagaimana saya membuat predikat prime? dan kenapa bilangan yang jadi masukan di sqrt-kan dahulu.

Predikat Pemeriksa Bilangan Prima

Cara yang gampang (tapi mahal O(n2)) memeriksa suatu bilangan apakah bilangan prima atau bukan adalah dengan memeriksa remainder bilangan p dibagi dengan bilangan mulai pn-1 sampai p1, jika remainder 0 hanya dibagi p dan 1, return true.

Cara agak cerdas adalah dengan algoritma Sieve of Eratosthenes. Yaitu dengan hanya memeriksa p di bawah √p. Selebihnya, saya tidak memeriksa bilangan genap juga.

Animasi berikut cukup menjelaskan bagaimana algoritma Sieve of Eratosthenes berkerja:

Sieve of Eratosthenes

Ide Sieve of Eratosthenes adalah mengeleminasi bilangan kelipatan dari bilangan di bawah √p. Dengan Clojure saya buat predikat prime? adalah sb brkt:

(defn abs [x]
  "Return absolute number of x."
  (if (>= x 0)
    x
    (- x)))
 
(def prime?
  (memoize
    (fn [x]
      "Return true if prime number."
      (let [x (abs x)]
        (cond
          (or (= x 0) (= x 1)) false
          (some (partion = x) [2 3 5 7 11 13 17]) true
          (even? x) false
          :else (->> (map #(zero? (rem x %))
                          (range 2 (-> x Math/sqrt int inc)))
                     (every? #(= false %))))))))

Kenapa Periksa dari √p

Tanpa Sieve of Eratosthenes, pencarian secara exhaustive berharga O(n2, bandingkan dengan Sieve of Eratosthenes yang O(n log log n). Optimize selebihnya selain menghilangkan bilangan genap, saya hanya melakukam memoization.

(def p3
  (memoize
    (fn [x]
      "Return largest prime factor."
      (let [p (int (Math/sqrt x))
            q (filter c/prime? (range 2 (inc p)))]
        (apply max (filter #(zero? (rem x %)) q))))))
 
(time (p3 600851475143))
;;=> "Elapsed time: 6185.461243 msecs"

6 detik! cukup lama, saya masih belum puas, akan saya optimize lagi. Harapan saya bisa dieksekusi kurang dari 1 detik. Once I get that, I will update to this blog!

{ 1 comment… add one }

Leave a Comment