Answer:
Explanation:
So your code has to pass the test
(check-equal? (sieve 10) (list 2 3 5 7))
This means, first, that (sieve 10) must be a valid call, and second, that it must return (list 2 3 5 7), the list of primes up to 10. 10 is a number,
(define (sieve n)
... so what do we have at our disposal? We have a number, n which can be e.g. 10; we also have (sieve-with divisors lst), which removes from lst all numbers divisible by any of the numbers in divisors. So we can use that:
(sieve-with (divisors-to n)
(list-from-to 2 n)))
list-from-to is easy to write, but what about divisors-to? Before we can try implementing it, we need to see how this all works together, to better get the picture of what's going on. In pseudocode,
(sieve n)
=
(sieve-with (divisors-to n)
(list-from-to 2 n))
=
(sieve-with [d1 d2 ... dk]
[2 3 ... n])
=
(foldl (lambda (d acc) (drop-divisible d acc))
[2 3 ... n] [d1 d2 ... dk])
=
(drop-divisible dk
(...
(drop-divisible d2
(drop-divisible d1 [2 3 ... n]))...))
So evidently, we can just
(define (divisors-to n)
(list-from-to 2 (- n 1)))
and be done with it.
But it won't be as efficient as it can be. Only the prime numbers being used as the divisors should be enough. And how can we get a list of prime numbers? Why, the function sieve is doing exactly that:
(define (divisors-to n)
(sieve (- n 1)))
Would this really be more efficient though, as we've intended, or less efficient? Much, much, much less efficient?......
But is (- n 1) the right limit to use here? Do we really need to test 100 by 97, or is testing just by 7 enough (because 11 * 11 > 100)?
And will fixing this issue also make it efficient indeed, as we've intended?......
So then, we must really have
(define (divisors-to n)
(sieve (the-right-limit n)))
;; and, again,
(define (sieve n)
(sieve-with (divisors-to n)
(list-from-to 2 n)))
So sieve calls divisors-to which calls sieve ... we have a vicious circle on our hands. The way to break it is to add some base case. The lists with upper limit below 4 already contain no composite numbers, namely, it's either (), (2), or (2 3), so no divisors are needed to handle those lists, and (sieve-with '() lst) correctly returns lst anyway:
(define (divisors-to n)
(if (< n 4)
'()
(sieve (the-right-limit n))))
And defining the-right-limit and list-from-to should be straightforward enough.
So then, as requested, the test case of 10 proceeds as follows:
(divisors-to 10)
=
(sieve 3) ; 3*3 <= 10, 4*4 > 10
=
(sieve-with (divisors-to 3)
(list-from-to 2 3))
=
(sieve-with '() ; 3 < 4
(list 2 3))
=
(list 2 3)
and, further,
(sieve 100)
=
(sieve-with (divisors-to 100)
(list-from-to 2 100))
=
(sieve-with (sieve 10) ; 10*10 <= 10, 11*11 > 10
(list-from-to 2 100))
=
(sieve-with (sieve-with (divisors-to 10)
(list-from-to 2 10))
(list-from-to 2 100))
=
(sieve-with (sieve-with (list 2 3)
(list-from-to 2 10))
(list-from-to 2 100))
=
(sieve-with (drop-divisible 3
(drop-divisible 2
(list-from-to 2 10)))
(list-from-to 2 100))
=
(sieve-with (drop-divisible 3
(list 2 3 5 7 9))
(list-from-to 2 100))
=
(sieve-with (list 2 3 5 7)
(list-from-to 2 100))
just as we wanted.