123k views
5 votes
sieve Impliment a function sieve that uses sieve-with to find all prime numbers and most n. This should be a relatively simple wrapper function that just sets up the right arguments to sieve-with. Note that not all potential divisors need to be checked, you can speed up your code a lot by stopping at the square root of the number you are testing. Here is a test case your code should pass:

1 Answer

4 votes

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.

User Enno Shioji
by
7.6k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.