# 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

- 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 11:30AM on Friday September 20.

# Marking

- This assignment will be worth 5% 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`