Remove Multiples
April 27, 2021
Today’s exercise comes from Stack Overflow:
Given a number N and a set of numbers s = {s1, s2, …, sn} where s1 < s2 < … < sn < N, remove all multiples of {s1, s2, …, sn} from the range 1..N.
You should look at the original post on Stack Overflow. The poster gets the answer wrong (he excludes 3), he get the explanation of his wrong answer wrong (he excludes 10 as a multiple of 2), and his algorithm is odd, to say the least. I’m not making fun of him, but I see this kind of imprecision of thought all the time on the beginner-programmer discussion boards, and I can only think that he will struggle to have a successful programming career.
Your task is to write a program that removes multiples from a range, as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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: