UNB/ CS/ David Bremner/ teaching/ cs2613/ assignments/ CS2613 Assignment 1

# 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

• You will be marked on the last version pushed to coursegit
• You will be marked on
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`