Background

• See Beautiful Racket unit testing explainer and Lab 3 for how to create a test suite.

• See the Beautiful Racket lists explainer and Section 2.3 of the Racket Guide for how to work with lists.

What to hand in, and how to hand it in, and when

• Make a directory ~fcshome/cs2613/assignments/A1 (i.e. in your git repo for this class). All files related to this assigment should be saved in that directory.
• Make sure you commit and push all your work using git before 16:30h on Friday September 23.

Marking

• This assignment will be worth 4% of your final grade.
• You will be marked on the last version pushed to coursegit
• You will be marked on

  adequacy of tests

  complete coverage is a minimum requirement

  coding style

  For racket, we follow official racket code layout. If you don't fight DrRacket too much, this should be easy. The construct guide is also interesting reading, but we will sometimes contradict it because we are learning the language, not developing a huge project.

  correctness

  Obviously your code should should do what it is supposed to.

  idiomatic racket

  The goal of this assignment is to learn about lists, recursion, and higher-order functions (filter and friends) in racket. Although racket supports mutation, you should not use it in this assignment. Avoid racket functions ending in !.

• For a detailed marking scheme, see racket-assignment

Questions

For questions 1 to 3, you should use only the functions included in #lang racket

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.

(module+ test
    (check-equal? (drop-divisible 3 (list 2 3 4 5 6 7 8 9 10)) (list 2 3 4 5 7 8 10)))

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. Here is a test your code should pass

(module+ test
    (check-equal? (sieve-with '(2 3) (list 2 3 4 5 6 7 8 9 10)) (list 2 3 5 7)))

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. Here is a test case your code should pass:

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

Q4 test against a second implimentation

Write another test for your code that

• imports the racket module math/number-theory only for the tests
• uses the function prime? from that module
• verifies that your code gets the same answers as prime? for n≤100000