2011/2/16 Marek Stępniowski <mstepniow...@gmail.com>:
> On Thu, Feb 17, 2011 at 12:34 AM, HB <hubaghd...@gmail.com> wrote:
>> I'm trying to write a function that determines if a number is a prime
>> or not.
>> Here is my first shot:
>>
>> (defn prime? [num]
>> (loop [i 2]
>> (if (<= (* i i) num)
>> false)
>> (recur (inc i)))
>> true)
>>
>> It is not working to be sure :)
>>
>> Please blow my mind with various implementations.
>
> It seems that you're mixing loop expression in Clojure with a Java
> loop. The loop in Clojure is just a binding and a point to which each
> recur will jump, instead of the start of function. You're lacking a
> stop condition in the loop.
>
> Here is the solution similiar to yours, but with a proper accumulator
> and stop condition:
>
> (defn prime? [n]
> (let [m (Math/sqrt n))]
> (loop [k 2]
> (cond
> (> k m) true
> (zero? (mod n k)) false
> true (recur (inc k))))))
>
> IMHO more idiomatic Clojure solution, using seq operations:
>
> (defn prime? [n]
> (if (< n 2)
> false
> (not-any? #(zero? (rem n %))
> (range 2 (min (inc (Math/sqrt n)) n)))))
This sometimes tests one higher number than it should:
user=> (defn prime? [n]
(if (< n 2)
false
(not-any? #(zero? (do (println %) (rem n %)))
(range 2 (min (inc (Math/sqrt n)) n)))))
#'user/prime?
user=> (prime? 47)
2
3
4
5
6
7
true
user=>
Coercing (Math/sqrt n) to int fixes this, as it truncates 6.92 to 6 so
it calls (range 2 7) rather than (range 2 7.92). The latter includes 7
and the former omits it. But if n is an integer square it makes no
difference: (Math/sqrt 49) is 7.0, (int 7.0) is 7, (inc 7) is 8, and
(range 2 8) includes 7, so (prime? 49) doesn't incorrectly report
true.
Perfect squares are also worst-case (other than actual primes), and
for positive integers greater than or equal to 2, the (min ... n)
around everything also should never make a difference, so:
(defn prime? [n]
(if-not (< n 2)
(let [x (Math/sqrt n)
y (int x)]
(if-not (== x y)
(not-any? #(zero? (do (println %) (rem n %)))
(range 2 (inc y)))))))
could be a bit more efficient. (It's likely to depend on your data. If
squares are common in the data this may help; if not the (== x y) test
may not be worth it.)
Another clear optimization is
user=> (defn prime? [n]
(if-not (< n 2)
(let [x (Math/sqrt n)
y (int x)]
(if-not (== x y)
(not-any? #(zero? (do (println %) (rem n %)))
(cons 2
(take-nth 2
(range 3 (inc y)))))))))
#'user/prime?
user=> (prime? 149)
2
3
5
7
9
11
true
This skips testing for divisibility by even numbers higher than 2.
In fact that can be taken further, to testing only divisibility by
/primes/ up to sqrt(n):
user=> (defn prime? [n]
(if-not (< n 2)
(let [x (Math/sqrt n)
y (int x)]
(if-not (== x y)
(not-any? #(zero? (do (println %) (rem n %)))
(filter user/prime? (range 2 (inc y))))))))
#'user/prime?
user=> (def prime? (memoize prime?))
#'user/prime?
user=> (prime? 149)
2
2
2
2
2
3
2
3
2
3
2
3
5
7
11
true
user=> (prime? 151)
2
3
5
7
11
true
user=>
This last of course gobbles memory remembering earlier primes. The
"user/prime?" is required in 1.2 for the function to call the memoized
version of itself that is created after. It might be desired to hoist
the var lookup out of the loop with
(defn prime? [n]
(if-not (< n 2)
(let [x (Math/sqrt n)
y (int x)]
(if-not (== x y)
(let [prime? user/prime?]
(not-any? #(zero? (do (println %) (rem n %)))
(filter prime? (range 2 (inc y)))))))))
and one can add further optimizations, particularly effective at large
n, by adding a probable-prime filter -- wrap the whole n >= 2 case in
(if (probable-prime? n) ...) and put a cheap probable-prime test in
probable-prime?, that is, a test that returns true reliably for prime
numbers and false for vast swathes of composite numbers. For truly
enormous n you'll want to lose the memoize/filter prime? part and
instead use filter probable-prime? on the range, as well as (if
(probable-prime? n) ...) around the bulk of the function, so as not to
blow the heap. Wikipedia will have plenty of information on
probable-prime tests, such as testing if a number is pseudo-prime to
some base (there are only 245 composite pseudo-primes to base 2 below
a million). Other probable-prime tests, such as randomly attempting
elliptic curve factorizations, come into their own for larger n. There
are also absolute primality tests that don't work by directly checking
divisibility by all the primes up to the number's square root, but
they are inefficient except for very large numbers, where they can
become superior. See http://en.wikipedia.org/wiki/Primality_test for
more on these topics.
Making all of this even more efficient is possible via resorting to
loop/recur with primitive math, of course.
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
