Function to find all prime numbers at most n in Racket

Question

I'm still pretty fresh to Racket so a bit confused about this, i've created a drop-divisible and sieve-with function as shown below with some help but now need to use both to create a single function that finds all prime numbers with a given length of a list.

(define (drop-divisible x lst)
  (cond 
    [(empty? lst) empty]
    [(or (= x (first lst)) (< 0 (remainder (first lst) x))) 
       (cons (first lst) (drop-divisible x (rest lst)))] 
    [else (drop-divisible x (rest lst))]))

(define (sieve-with divisors lst)
  (foldl (lambda (e acc) (drop-divisible e acc))
         lst divisors))

this is one of the test cases i need to pass

(module+ test
  (check-equal? (sieve 10) (list 2 3 5 7)))

so far ive tried to create a list using the parameter given with sieve to create a list of that size.

(define (sieve lst)
  ((sieve-with () (build-list (sub1 lst) (+ values 2)))))

getting stuck on how to get the divisors from just 10 in the test case. Thanks

Answer 1

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.

Answer 2

I guess this is an assignment 1 from CS2613. It would be helpful to add an exact description of your problems:

Q1: drop-divisible

Using (one or more) higher order functions filter, map, foldl, foldr (i.e. no explicit recursion), write a function drop-divisible that takes a number and a list of numbers, and returns a new list containing only those numbers not "non-trivially divisible". In particular every number trivially divides itself, but we don't drop 3 in the example below.

You are required to write drop-divisible using higher order functions (map, filter, foldl and so on), with no explicit recursion. Your drop-divisible is definitely recursive (and probably copied from this question).

Q2: sieve-with

Using drop-divisible and explicit recursion write a function that takes a list of divisors, a list of numbers to test, and applies drop-divisible for each element of the list of divisors.

Q3: 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.

Function sieve will call sieve-with with two arguments: a list of divisors and a list of all numbers to be sieved. You will need function range to create these lists and also sqrt to get the square root of the given number.