Clojure - tail recursive sieve of Eratosthenes

Posted by Konrad Garus on Stack Overflow See other posts from Stack Overflow or by Konrad Garus
Published on 2010-06-05T13:48:11Z Indexed on 2010/06/05 13:52 UTC
Read the original article Hit count: 342

Filed under:

algorithm

|

clojure

|

functional

I have this implementation of the sieve of Eratosthenes in Clojure:

(defn sieve [n]
  (loop [last-tried 2 sift (range 2 (inc n))]
    (if
      (or (nil? last-tried) (> last-tried n))
      sift
      (let [filtered (filter #(or (= % last-tried) (< 0 (rem % last-tried))) sift)]
        (let [next-to-try (first (filter #(> % last-tried) filtered))]
        (recur next-to-try filtered))))))

For larger n (like 20000) it ends with stack overflow. Why doesn't tail call elimination work here? How to fix it?

© Stack Overflow or respective owner

Related posts about algorithm

Jpeg Algorithm vs BMP Algorithm?

as seen on Super User - Search for 'Super User'
I'm just wonder, what the differences are between creating a BMP file algorithm and JPG file algorithm ? If you know the others images' format algorithm, please post them. Thanks. >>> More
word disambiguation algorithm (Lesk algorithm)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hii.. Can anybody help me to find an algorithm in Java code to find synonyms of a search word based on the context and I want to implement the algorithm with WordNet database. For example, "I am running a Java program". From the context, I want to find the synonyms for the word "running", but the… >>> More
Search algorithm (with a sort algorithm already implemented)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, Im doing a Java application and Im facing some doubts in which concerns performance. I have a PriorityQueue which guarantees me the element removed is the one with greater priority. That PriorityQueue has instances of class Event (which implements Comparable interface). Each Event is associated… >>> More
Is there any algorithm for finding LINES by PIXEL COLORS on picture?

as seen on Stack Overflow - Search for 'Stack Overflow'
So I have Image like this I want to get something like this (I hevent drawn all lines I want but I hope you can get my idea) I need algorithm for finding all straight lines on it by just reading colors of pixels. No hard math, no Haar, no Hough. Some algorithm which would be based on points… >>> More
collsion issues with quadtree [on hold]

as seen on Game Development - Search for 'Game Development'
So i implemented a Quad tree in Java for my 2D game and everything works fine except for when i run my collision detection algorithm, which checks if a object has hit another object and which side it hit.My problem is 80% of the time the collision algorithm works but sometimes the objects just go… >>> More

Related posts about clojure

StackOverflow in compojure web project

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi I've been playing around with clojure and have been using it to build a simple little audio player. The strange thing is that sometimes, maybe one out of twenty, when contact the server I will get the following error: 2010-04-20 15:33:20.963::WARN: Error for /control java.lang.StackOverflowError … >>> More
Wrong number of args passed to: repl$repl

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, I have a trouble with a compojure "Getting started" example that I do not seem to understand. When I run the example from http://weavejester.github.com/compojure/docs/getting-started.html ...I get the following error at the lein repl step: ~/hello-www> lein repl src/hello_www/core.clj Exception… >>> More
Setting the Classpath and Accessing code from book: Programming Clojure

as seen on Stack Overflow - Search for 'Stack Overflow'
(I posted this same question on the Clojure list but haven't got an answer yet. Is anyone here ready to help?) I am going through Programming Clojure and I recently downloaded the code from the books official website. For other utils I can do, for example, (require 'clojure.contrib.str-utils) and… >>> More
How can I define a clojure type that implements the servlet interface?

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm attempting to use deftype (from the bleeding-edge clojure 1.2 branch) to create a java class that implements the java Servlet interface. I would expect the code below to compile (even though it's not very useful). (ns foo [:import [javax.servlet Servlet ServletRequest ServletResponse]]) (deftype… >>> More
Stack overflow in compojure web project

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi I've been playing around with clojure and have been using it to build a simple little audio player. The strange thing is that sometimes, maybe one out of twenty, when contacting the server I will get the following error: 2010-04-20 15:33:20.963::WARN: Error for /control java.lang.StackOverflowError … >>> More