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.
Programming Praxis 
Cool little drill. Here is my take on it using Julia 1.6: https://pastebin.com/MjmG6b8f
;; This looks like eratostene sieve (defun remove-multiples (up-to factors) (check-type up-to (integer 1)) (check-type factors list) (let ((numbers (make-array (1+ up-to) :element-type 'bit :initial-element 1))) (dolist (factor factors) (loop :for n :from factor :to up-to :by factor :do (setf (aref numbers n) 0))) (loop :for i :from 1 :to up-to :when (plusp (aref numbers i)) :collect i))) (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);; This looks like eratostene sieve (defun remove-multiples (up-to factors) (check-type up-to (integer 1)) (check-type factors list) (let ((numbers (make-array (1+ up-to) :element-type 'bit :initial-element 1))) (dolist (factor factors) (unless (zerop (aref numbers factor)) ; avoid useless work (loop :for n :from factor :to up-to :by factor :do (setf (aref numbers n) 0)))) (loop :for i :from 1 :to up-to :when (plusp (aref numbers i)) :collect i))) (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)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:
(define (remove-multiples N s) (let loop ((n 1) (out '())) (if (> n N) (reverse out) (loop (add1 n) (if (foldl (λ (a i) (and i (not (zero? (modulo n a))))) #t s) (cons n out) out)))))Examples:
Here’s a Haskell version.
Here’s a solution in Python.
def remove_multiples(N, s): keep = [True] * N for x in s: if keep[x - 1]: for y in range(x, N + 1, x): keep[y - 1] = False return [idx + 1 for idx, x in enumerate(keep) if x] print(remove_multiples(100, [2, 3, 5, 7, 11, 13, 19]))Output:
Here’s a solution in C using a bit array.
#include <stdio.h> #include <string.h> void remove_multiples(int n, int* s, int s_len, char* keep) { memset(keep, 0xFF, (n + 7) / 8); for (int i = 0; i < s_len; ++i) { int x = s[i]; if (!(keep[(x - 1) / 8] & (1 << ((x - 1) % 8)))) continue; for (int y = x; y <= n; y += x) keep[(y - 1) / 8] &= ~(1 << ((y - 1) % 8)); } } int main(void) { int s[] = {2, 3, 5, 7, 11, 13, 19}; int s_len = sizeof(s) / sizeof(int); int n = 100; int num_bytes = (n + 7) / 8; char keep[num_bytes]; remove_multiples(n, s, s_len, keep); for (int i = 0; i < n; ++i) { if (keep[i / 8] & (1 << (i % 8))) printf(" %d", i + 1); } printf("\n"); return 0; }Output: