## Remove Multiples

### April 27, 2021

The obvious solution is a sieve, similar to the Sieve of Eratosthenes. But we’ll do something different, just for fun:

(define (del-mult n ss) (list-of x (x range 1 (+ n 1)) (all? positive? (map (lambda (s) (modulo x s)) ss)))) > (del-mult 10 '(2 4 5)) (1 3 7 9)

You can run the program at https://ideone.com/6Jgqx7.

Cool little drill. Here is my take on it using Julia 1.6: https://pastebin.com/MjmG6b8f

I’d agree that this is like the Sieve of Eratosthenes, but isn’t the latter specialized in prime numbers? I imagine the numbers in s can be any positive integers, making the problem subject to optimizations that relate to the absence of relative primeness among the members of s. Just a thought…

@Zack: If you think of this as a sieving process, the simplest optimization is to process the integers in the set in increasing order, omitting any that are already crossed off. For instance, in the sample set {2, 4, 5}, there is no need to sieve on 4 because any integers divisible by 4 have already been eliminated by sieving on 2.

(define (range a b)

(if (> a b) ‘() (cons a (range (+ 1 a) b))))

(define (remove-multiples n ss)

(let loop ((ns (range 1 n))

(ss ss))

(if (null? ss)

ns

(let ((mults (map (lambda (x) (* x (car ss)))

(range 1 (div n (car ss))))))

(loop (remp (lambda (x) (member x mults)) ns)

(cdr ss))))))

> (remove-multiples 100 ‘(2 3 5 7 11 13 19))

(1 17 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)

@programmingpraxis. That’s exactly my point in the previous comment (also, what I’ve done in my solution). If we allow for numbers that are not relative primes to each other in S, then this optimization makes sense. Otherwise, if we just use a list of primes, it’s just like the Sieve of Eratosthenes. In any case, it’s a cool little drill.

A solution in Racket:

Examples:

Here’s a Haskell version.

Here’s a solution in Python.

Output:

Here’s a solution in C using a bit array.

Output: