## 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.

Pages: 1 2

### 11 Responses to “Remove Multiples”

1. Zack said

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

2. ```;; 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)

```
3. pjbinformatimagocom said
```;; 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)
```
4. Zack said

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…

5. programmingpraxis said

@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.

6. indathrone said

(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)

7. Zack said

@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.

8. Kevin said

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:

```> (remove-multiples 20 '(3 5 10))
'(1 2 4 7 8 11 13 14 16 17 19)
> (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)
```
9. Globules said

```rems :: Integral a => a -> [a] -> [a]
rems n = foldl (\ns s -> filter ((/= 0) . (`rem` s)) ns) [1..n]

main :: IO ()
main = do
print \$ rems ( 10 :: Int) [2, 4,  5]
print \$ rems ( 20 :: Int) [3, 5, 10]
print \$ rems (100 :: Int) [2, 3,  5, 7, 11, 13, 19]
```
```\$ ./remmults
[1,3,7,9]
[1,2,4,7,8,11,13,14,16,17,19]
[1,17,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
```
10. Daniel said

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:

```[1, 17, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
```
11. Daniel said

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:

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