**Problem 2.7.1:** Design an algorithm that counts the number of digits in an integer.

Again, not a super interesting problem but one which we can solve for free. And I love free stuff.

1 2 3 4 |
user=> (count (get-digits 2345)) 4 user=> (count (get-digits 890)) 3 |

So is the next one.

**Problem 2.7.2:** Design an algorithm to sum the digits in an integer.

1 2 3 4 |
user=> (reduce + (get-digits 2345)) 14 user=> (reduce + (get-digits 890)) 17 |

And this one is good too.

**Problem 2.7.3:** Design an algorithm that reads in a set of n single digits and converts them into a single decimal integer. For example, the algorithm should convert the set of 5 digits {2,7,4,9,3} to 27493.

1 2 |
user=> (reduce + (map-indexed get-multiplied (reverse [2 7 4 9 3]))) 27493 |

And that’s why it’s cool to make small complete functions without side-effects. Reusability, baby.

**Problem 3.4.2:** It is possible to implement a sieving algorithm which crosses out each composite (non-prime) number exactly once rather than a number of times. […] Try to implement this algorithm aka. Sieve of Eratosthenes.

The wikipedia page got a cool animation of this algorithm. It’s a great starting point to start with this.

Let’s make this interactive. I start with a list of all integers from 2 to 40:

1 2 3 4 |
user=> (def numbers (take 39 (iterate inc 2))) #'user/numbers user=> numbers (2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40) |

Now, imagine we know already that 2 is a prime number.

1 2 3 4 |
user=> (def primes [2]) #'user/primes user=> primes [2] |

What we would now do is remove every number which is a multiple by 2. Or whose characteristic is mod 2 = 0.

1 2 |
user=> (remove #(= 0 (rem % (first primes))) numbers) (3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39) |

Neat. Now we just need to find the next prime. We know that the next bigger number in our number list is a prime, in this case 3. And then we start again.

Let’s write a function:

1 2 3 4 5 6 7 8 9 10 11 |
(defn prime-sieve "Generates all primes up to n using the Sieve of Eratosthenes" [n] {:pre [(> n 1)]} (loop [primes nil numbers (take (dec n) (iterate inc 2))] (if (seq numbers) (recur (conj primes (first numbers)) (remove #(= 0 (rem % (first numbers))) numbers)) primes))) |

I was surprised how small and easy to function is. Let’s go through it. We start easily with creating a list of numbers, like before. It starts with 2 and ends with n. Also we have an empty collection primes in which we put our primes. We know that the first element of our list `numbers`

is always a prime, so we can put that into there. The next step is to remove all multiplies of that prime in our list. Now we just recursively call that function again. This runs so long until there’s no number left in `numbers`

and the function returns our – now – big list of primes.

1 2 3 4 |
user=> (prime-sieve 20) (19 17 13 11 7 5 3 2) user=> (prime-sieve 60) (59 53 47 43 41 37 31 29 23 19 17 13 11 7 5 3 2) |

Neat.