Check a given is prime or not using clojure

Question

(defn prime [x]
    (if (#(<= % (Math/sqrt x)) (first (filter zero? (mod x (range 2 (inc x))))))
       false
       true))

Hi there! I want to check the given number is prime or not using clojure. Firstly, I want to filter all the divisors of x, then select the first number of these divisors. Finally, comparing to the square root of x, if the first divisor is smaller or equal to x, then the given number is not a prime. Otherwise, it is. However, when I run the code, I got such an error. How can I figure out the problem that convert a Lazyseq to a Number? I would appreciate if anyone can help me!

posting the error in your question would help – mattexx Jan 26 '16 at 22:56 — mattexx, Jan 26 '16 at 22:56

score 3 · Answer 1 · edited May 23 '17 at 12:09

I think the problem is slightly different. We do not want to try values greater than the square root of the number we want to know is prime or not. Reason is explain in this SO. (Basically if x = a * b, then both a AND b cannot be greater than the square root)

So the sequence we are building, is up to the square root

(defn root-1 [x]
    (inc (long (Math/sqrt x))))

(defn range-1 [x]
  (range 2 (root-1 x)))

Finally, we are filtering on divisor:

(defn filter-1 [x]
  (filter #(zero? (rem x %))
        (range-1 x)))

And especially, we can stop at the first one, and filter being lazy, that comes up nicely with:

(defn is-prime [x]
  (nil? (first (filter-1 x))))

Which we can try with:

(is-prime 10) ; false
(is-prime 11) ; true

score 1 · Answer 2 · answered Apr 14 '17 at 16:37

Fast check that number is prime:

(ns example.core
  (:gen-class)
  (:require [clojure.core.reducers :as r]))


(defn prime-number?
  [n]
  (let [square-root (Math/sqrt n)
        mod-zero? (fn [res new-val]
                    (if (zero? (mod n new-val))
                      (reduced false)
                      true))]
    (r/reduce mod-zero? true (range 2 (inc square-root)))))

(prime-number? 2147483647)
;=> true

Shlomi · Answer 3 · 2016-01-27T09:35:25.123

0

Two comments:

range returns a seq, which you are trying to apply (mod x ...) to. I think you are missing a map..
There is no real point in returning true and false from an if, if you think about it ;) (hint, try to see how the function not behaves)

You should make another attempt and update us on what you came up with!

edited Jan 27 '16 at 09:35

answered Jan 26 '16 at 23:14

Shlomi

4,708
1
23
32

score 0 · Answer 4 · answered Jan 27 '16 at 12:31

Paraphrasing your recipe:

Filter all the divisors of x.
Select the first of these.
If it is smaller then or equal to the square root of x, then x is not a prime.

The given code has the problems:

The surrounding if form is redundant.
The filter function is wrong. It ought to incorporate the zero? and the mod x.
There is no need to construct and apply an anonymous function. Just apply the test directly.

And, though the repaired algorithm would work, it is still clumsy.

The first divisor of a prime x is x itself. There is no need to muck about with square roots.
The range ought to be from 2 to the square root of x. Then a nil value for the first divisor indicates a prime.

Check a given is prime or not using clojure

4 Answers4