Question

Read about the Sieve of Sundaram. Implement the algorithm using function composition.

Given an integer n, your function should generate all the odd prime numbers up to 2n+2.

sieveSundaram :: Integer -> [Integer]

sieveSundaram = ...

To give you some help, below is a function to compute the Cartesian product of two lists.

This is similar to zip, but it produces all possible pairs instead of matching up the list

elements. For example,

cartProd [1,2] ['a','b'] == [(1,'a'), (1,'b'), (2,'a'), (2,'b')]

It's written using a list comprehension, which we haven't talked about in class (but feel free

to research them).

cartProd :: [a] -> [b] -> [(a,b)]

catProd xs ys = [(x,y) | x <- xs, y <- ys]

Answer 1

code

solution

Note:programming language is not given.I am using racket program code

//output

//output

//copyable code

1.

#lang racket

(define (sievesundaram num)

(define primes1 (make-vector (add1 num) #t))

(for* ([k (in-range 2 (add1 num))]

         #:when (vector-ref primes1 k)

         [j1 (in-range (* k k) (add1 num) k)])

    (vector-set! primes1 j1 #f))

(for/list ([num (in-range 2 (add1 num))]

             #:when (vector-ref primes1 num))

    num))

(sievesundaram 20)

2.

#lang racket

;require data

(require rackunit

(only-in racket/list cartesian-product))

;; check the data

(check-equal? (cartesian-product '(7 4) '(2 4))

             '((7 2) (7 4) (4 2) (4 4)))

;;test data

(cartesian-product '(1 2)'(a b))