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


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



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