(defn lazy-primes [] (letfn [(enqueue [sieve n step] (let [m (+ n step)] (if (sieve m) (recur sieve m step) (assoc sieve m step)))) (next-sieve [sieve candidate] (if-let [step (sieve candidate)] (-> sieve (dissoc candidate) (enqueue candidate step)) (enqueue sieve candidate (+ candidate candidate)))) (next-primes [sieve candidate] (if (sieve candidate) (recur (next-sieve sieve candidate) (+ candidate 2)) (cons candidate (lazy-seq (next-primes (next-sieve sieve candidate) (+ candidate 2))))))] (cons 2 (lazy-seq (next-primes {} 3)))))and this one that is very close to what I wanted:

(defn sieve [n] (let [n (int n)] "Returns a list of all primes from 2 to n" (let [root (int (Math/round (Math/floor (Math/sqrt n))))] (loop [i (int 3) a (int-array n) result (list 2)] (if (>= i n) (reverse result) (recur (+ i (int 2)) (if (< i root) (loop [arr a inc (+ i i) j (* i i)] (if (>= j n) arr (recur (do (aset arr j (int 1)) arr) inc (+ j inc)))) a) (if (zero? (aget a i)) (conj result i) result)))))))and of course the one from contrib:

(defvar primes (concat [2 3 5 7] (lazy-seq (let [primes-from (fn primes-from [n [f & r]] (if (some #(zero? (rem n %)) (take-while #(<= (* % %) n) primes)) (recur (+ n f) r) (lazy-seq (cons n (primes-from (+ n f) r))))) wheel (cycle [2 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4 8 6 4 6 2 4 6 2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10])] (primes-from 11 wheel)))) "Lazy sequence of all the prime numbers.")Instead I came up with my own bad one...

(defn primes [max-num]( loop [numbers (range 2 max-num) primes [] p 2] (if (= (count numbers) 1) (conj primes (first numbers)) (recur (filter #(not= (mod % p) 0) numbers) (conj primes p) (first (rest numbers))))))Why is this so bad? Well it is horribly inefficient. It creates a list of integers up to the max-num that is the only input to the function. It then loops, each time removing all multiples of each prime -- just like a sieve is supposed to. However, most sieves take a prime p and remove 2p, 3p, 4p, etc. (often optimized to 3p, 5p, 7p, since all the even numbers are removed at the beginning.) This does the same thing, but it uses a filter to do it. So it goes through each member of the list to check if it is divisible by p. So it does way too many calculations. Next, it is constantly generating a new list of numbers to pass back into the loop. Maybe Clojure does some cleverness to make this not as memory inefficient as it sounds, but I don't think so.

So what is it that I did not like about the other many examples out there or suggested by the community? Most of them used a lazy sequence. That's great and very efficient. However, it's not a concept that is easy to implement in other, less functional languages (Go Clojure!) On the other hand, the Rich Hickey example is much closer to what I wanted to do. However, it uses Java arrays. There is no duplication of the list and the non-primes are eliminated efficiently. Using Java arrays just seems non-idiomatic to say the least. The other examples did for JavaOne all used variable length lists instead of arrays.

Anyways, I am satisfied to at least have a seemingly equivalent, idiomatic Clojure implementation. I looked at optimizing it through using type hints. I actually had to use a lot of type hints (4) to get a 10% decrease in speed. Anyways, not that this is out here, others will improve it, as that shouldn't be too hard to do!

## 1 comment:

We are a third party technical support service.

Avast Customer Supportis here to help you out with the whole procedure to DownloadAvast Antivirusonline, We not only fix yourAvast Supportrelated issues but will guide with how to get started with your new Avast product once it gets installed successfully.We atAvast Tech Supportprovides service to protect your PC from potential online threats and external attacks like viruses, Trojans, malwares, spywares and phishing scams. AndAvast Refund. Call on ourAvast Phone Number.Gmail Customer serviceis a third party technical support service for Gmail users when they face any technical issue or error in their Gmail account. OurGmail Customer Supportteam solves issues like forgot Gmail account password, Gmail configuration or Sync issues, recover deleted emails and many more. Toll Free number (800) 986-9271How you install or reinstall Office 365 or Office 2016 depends on whether your Office product is part of an Office for home or Office for business plan. If you're not sure what you have, see what

office com setupproducts are included in each plan and then follow the steps for your product. The steps below also apply if you're installing a single, stand-alone Office application such as Access 2016 or Visio 2016. Need Help withoffice setupEnter Product Key? Call 1-800-000-0000 Toll FreeNorton Tech Supportis a third party service provider and not in any way associated with Norton or any of its partner companies. We offer support for Norton products and sell subscription based additional warranty on computer and other peripheral devices. Call our Toll Free number 1 855 966 3855Other Services

Post a Comment