Reputation: 154
I'm learning Clojure and I've just started on Project Euler and I've run into a problem I cannot figure out. Here is my code:
(defn largest_prime_factor
[x]
(if (prime? x) x)
(loop [running x divider 2]
(if (= 0 (mod running divider))
(let [d (/ running divider)]
(if (prime? d)
d
(recur d 2)))
(recur x (inc divider)))))
(largest_prime_factor 12) ;works
(largest_prime_factor 49) ;works
(largest_prime_factor 147) ;Endless loop!
I realise that this might not be the most efficient way to find the largest prime factor but what I'm trying to figure out is why it gets stuck in a loop. Obviously I'm using loop-recur the wrong way but what am I doing wrong?
Upvotes: 2
Views: 149
Reputation: 26466
A couple of things
(defn largest_prime_factor
[x]
(if (prime? x) x) ; #1
(loop [running x divider 2]
(if (= 0 (mod running divider))
(let [d (/ running divider)]
(if (prime? d)
d
(recur d 2)))
(recur x (inc divider))))) ; #2
The extra closing parenthesis makes this a self-contained if
without an else
clause. This has no bearing on the infinite loop, but would give the wrong answer (1) for a prime input (unless you start your divider at 1 instead, in which case you can omit this initial test).
This line should recur with running
rather than x
, otherwise you have not factored out the divisor and the prime?
test will ever after be false. This is why you wind up in an infinite loop.
Upvotes: 3