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.

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

    Here’s a Haskell version.

    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
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: