He estado buscando en la web una implementación del Sieve of Eratosthenes en el esquema y, aunque encontré una gran cantidad de contenido, ninguno de ellos parecía haberlo hecho como si fuera necesario.

El problema es que la mayoría de los algoritmos usan un final estático o usan iteración. Esto, junto con mi falta de conocimiento del idioma, me llevó a pedirles ayuda a todos ustedes.

Necesito una implementación del Sieve que incluya un argumento (número para Sieve hasta), use solo recursividad y tenga una lista de "contras" de un número con un#t (verdad o#f (falso).

Así que esencialmente el algoritmo iría como tal:

Haga una lista del 2: número incorporado con cada número que comienza como verdaderoRecurre y marque cada número que es divisible por 2 falsouego, continúe con el siguiente número "verdadero" de la lista hasta que solo queden números primos marcados como verdadero Salir de la lista

Salida de ejemplo:

> (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))

Si también pudieras tener comentarios que expliquen a fondo el código, sería muy apreciado.

¡Gracias

REVISAD ::: Así que aprendí un poco de esquema para explicar más mi pregunta ...

Esto hace la lista.

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

Esto devuelve una lista con cada múltiplo del divisor marcado como falso.

(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))))

Ahora esta es la función con la que tengo problemas, parece que debería funcionar, lo he revisado manualmente tres veces, pero no puedo entender por qué no me devuelve lo que necesito.

(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))))))

Lo que estoy tratando de hacer es, como sugiere el nombre de la función, llamar a múltiplos de marcado para cada número que todavía está marcado como verdadero en la lista. Entonces pasas((3.#t)(4.#t)(5.#t)) y luego llama amark-off-multiples para 2 y devuelve(3.#t)(4.#f)(5.#t) y anexas(2.#t) a eso. Luego se llama a sí mismo nuevamente pasando(3.#t)(4.#f)(5.#t) y llama múltiplos de marcado con el cdr de la lista que devuelve(4.#f)(5.#t) y sigue bajando por la lista ...

La salida que luego recibo es una lista con todas las verdades.

Esto, espero que con tu ayuda entiendas mejor mi situación.