recursion - Sieve of Eratosthenes Scheme

Question

I've been searching the web for an implementation of the Sieve of Eratosthenes in scheme and although I came up with a lot of content, none of them seemed to have made it like I need it to be done.

The problem is most algorithms either use a static end or use iteration. This paired with my lack of knowledge of the language led me to ask all of you for help.

I need an implementation of the Sieve that takes in one argument (number to Sieve until), uses only recursion and has a list of "cons" of a number with a #t (true) or #f (false).

So essentially the algorithm would go as such:

1. Make list from 2 - inputed number with each number starting as true
2. Recursively go through and mark each number that is divisible by 2 false
3. Then go on to the next "true" number in the list until only primes are left marked true
4. Output the list

Example output:

> (erat-sieve 20)

((2 . #t) (3 . #t) (4 . #f) (5 . #t) (6 . #f) (7 . #t) (8 . #f) (9 . #f) (10 . #f) (11 . #t) (12 . #f) (13 . #t) (14 . #f) (15 . #f) (16 . #f) (17 . #t) (18 . #f) (19 . #t) (20 . #f))

If you could also have comments thoroughly explaining the code, that would be extremely appreciated.

Thank you!

REVISED::: So I've learned a bit of scheme to further explain my question...

This makes the list.

(define (makeList n)
 (if (> n 2)
  (append (makeList (- n 1)) (list (cons n (and))))
  (list (cons 2 (and)))))

This returns a list with each multiple of the divisor marked false.

(define (mark-off-multiples numbers divisor)
 (if (null? numbers)
  '()
  (append 
     (list (cons (car (car numbers)) 
                 (not (zero? (modulo (car (car numbers)) divisor))))) 
     (mark-off-multiples (cdr numbers) divisor))))

Now this is the function I'm having trouble with, it seems like it should work, I've gone through it manually three times, but I can't figure out why its not returning what I need.

(define (call-mark-off-multiples-for-each-true-number numbers)
 (if (null? numbers)
  '()
  (if (cdr (car numbers))
    (append (list (car numbers))
            (call-mark-off-multiples-for-each-true-number 
               (mark-off-multiples (cdr numbers) (car (car numbers)))))
    (append (list (car numbers))
            (call-mark-off-multiples-for-each-true-number 
               (cdr numbers))))))

What I'm trying to make it do is, as the function name suggests, call mark-off-multiples for each number that is still marked true down the list. So you pass in ((3.#t)(4.#t)(5.#t)) and then it calls mark-off-multiples for 2 and returns (3.#t)(4.#f)(5.#t) and you append (2.#t) to it. Then it calls itself again passing in (3.#t)(4.#f)(5.#t) and calls mark-off-multiples with the cdr of the list returning (4.#f)(5.#t) and keeps going down the list...

The output I then get returned is a list with all trues.

This, hopefully with help you better understand my predicament.

Answer 1

Here is a solution that works.

(define (divides? m n)
  (if (eq? (modulo n m) 0)
      #t
      #f))

(define (mark-true n)
  (cons n #t))

(define (mark-divisors n ns)
  (cond ((null? ns) '())
        ((and (unmarked? (car ns)) 
              (divides? n (car ns))) 
           (cons (cons (car ns) #f) (mark-divisors n (cdr ns))))
        (else (cons (car ns) (mark-divisors n (cdr ns))))))

(define (unmarked? n)
  (not (pair? n)))

(define (eratosthenes x)
  (cond ((null? x) '())
        ((unmarked? (car x)) 
           (cons (mark-true (car x)) 
                 (eratosthenes (mark-divisors (car x) (cdr x)))))
        (else (cons (car x) (eratosthenes (cdr x))))))

(eratosthenes (list 2 3 4 5 6))

I've used a number of helper functions, but you could add them to the eratosthenes function if you wanted. I think it makes this whole business more readable.

mark-true conses a value onto a #t. mark-divisors takes a number n and a list of numbers and conses all of the numbers that n divides onto a #f. Pretty much everything else is self explanatory. Eratosthenes works as it should, if the first digit is "unmarked" it marks it as "true" or "prime" and then "crosses out" all of its multiples from the remainder of the list and then repeats for each subsequent "unmarked" digit in the list. My eratosthenes function does essentially what you were trying to do with yours. I'm not sure what the problem with yours is, but as a rule, it's helpful to make helpers to make your stuff more readable.

I did this in DrRacket with Neil Van Dyke's SICP package. I don't know what Scheme you're using. Let me know if you have problems getting this to work.