small medium large xlarge

Section 3.3, you coul avoid using the factor ring as I think it’s non obvious whats going on

(def primes-simple (concat [2 3 5 7] (lazy-seq (let [primes-from (fn primes-from [n] (if (some #(zero? (rem n %)) (take-while #(<= (* % %) n) primes-simple)) (recur (+ n 1)) (lazy-seq (cons n (primes-from (+ n 1))))))] (primes-from 11)))))

I agree! I’ve been writing Clojure code for two years and I can’t figure out how this code works. (I’m reading the beta 5 book, page 71.)

I’m rereading the book (I also have the original Programming Clojure book) from the start, and this code is much harder than all the other code so far. Without some qualification in the text (e.g., “Don’t worry about not understanding this…”), this is very jarring.

On a freshly installed leiningen, it doesn’t even compile:

``` CompilerException java.lang.RuntimeException: Unable to resolve symbol: primes in this context, compiling:(NO_SOURCE_PAT H:8) RuntimeException Unmatched delimiter: ) clojure.lang.Util.runtimeException (Util.java:170) ```

The confusion with the primes example is to do with the “wheel” hard-wired cycle. I had no idea what it was doing until I read the paper The Genuine Sieve of Eratostheses.

The “wheel” is a generalisation of the removal of multiples of 2 from the test for primes. It is a repeating sequence of offsets from one non-multiple to the next of the initial set of primes. Why “wheel”? The process can be visualised as a wheel rolling along the number line. At certain points in the circumference, there is a hole, which allows the corresponding number to pop through. These numbers can then be tested for further factors (beyond the starting set.) The numbers that have been “crushed” by the wheel are those that are a multiple of one or more of the initial set of primes.

The basis of the cycle is the set of integers from 1 to the lowest common multiple of the initial set of primes.

For example, with an initial set of `[2 3]`, the cycle length is `(* 2 3) => 6`. The non-multiples in the first set of 6 integers are `[1 5]`. These are the only candidates as prime (apart from the initial set of [2 3].)

The following sets are simply incremented by the cycle length; so `[1 5] [7 11] [13 17]`. The increments are `1->5->7->11->13` etc. That is, `4, 2, 4, 2` etc, which is a repeating cycle of `[4 2]`. With a starting set of `[2 3]`, the first candidate is 5, and the starting point of the increments cycle is `5->7`; i.e. 2. Note that the cycle of increments can be started at whatever point is required, and this applies to cycles of any length.

The initial set in this case is `[2 3 5 7]`. The L.C.M is 210, and the increment cycle begins `1->11->13->17->19->23->29->31`; i.e. `10, 2, 4, 2, 4, 6, 2`.

Because our starting point is always the first candidate following the last of the starting set, we always skip the first increment, which will recur at the beginning of the next cycle. So the wheel starts `[2 4 2 4 6 2...]` and ends with the wrap-around to 10.

The same offsets will apply to all subsequent cycles of 210 integers; hence wheel is defined as a cycle on the vector of candidate offsets.

You must be logged in to comment