Remove all the multiples of a given set of numbers from given range

Question

I am stuck on a problem, where it says, given a number N and a set of numbers, S = {s1,s2,.....sn} where s1 < s2 < sn < N, remove all the multiples of {s1, s2,....sn} from range 1..N

Example:

Let N = 10
S = {2,4,5}
Output: {1, 7, 9}
Explanation: multiples of 2 within range: 2, 4, 6, 8
             multiples of 4 within range: 4, 8
             multiples of 5 within range: 5, 10

I would like to have an algorithmic approach, psuedocode rather than complete solution.

What I have tried:

(Considering the same example as above) 

 1. For the given N, find all the prime factors of that number.
    Therefore, for 10, prime-factors are: 2,3,5,7
    In the given set, S = {2,4,5}, the prime-factors missing from 
    {2,3,5,7} are {3,7}.  
 2. First, check prime-factors that are present: {2,5}
    Hence, all the multiples of them will be removed 
    {2,4,5,6,8,10}
 3. Check for non-prime numbers in S = {4}
 4. Check, if any divisor of these numbers has already been 
    previously processed.
         > In this case, 2 is already processed.
         > Hence no need to process 4, as all the multiples of 4 
           would have been implicitly checked by the previous 
           divisor.
    If not,
         > Remove all the multiples from this range.
 5. Repeat for all the remaining non primes in the set.

Please suggest your thoughts!

score 4 · Accepted Answer · answered Dec 23 '17 at 08:23

It is possible to solve it in O(N log(n)) time and O(N) extra memory using something similar to the Sieve of Eratosthenes.

isMultiple[1..N] = false

for each s in S:
    t = s
    while t <= N:
        isMultiple[t] = true
        t += s

for i in 1..N:
    if not isMultiple[i]:
        print i

This uses O(N) memory to store the isMultiple array.

The time complexity is O(N log(n)). Indeed, the inner while loop will be performed N / s₁ times for the first element in S, then N / s₂ for the second, and so on.

We need to estimate the magnitude of N / s₁ + N / s₂ + ... + N / s_n.

N / s₁ + N / s₂ + ... + N / s_n = N * (1/s₁ + 1/s₂ + ... + 1/s_n) <= N * (1/1 + 1/2 + ... + 1/n).

The last inequality is due to the fact that s₁ < s₂ < ... < s_n, thus the worst case is when they take values {1, 2, .. n}.

However, the harmonic series 1/1 + 1/2 + ... + 1/n is in O(log(n)), (e.g. see this), thus the time complexity of the above algorithm is O(N log(n)).

score 1 · Answer 2 · answered Dec 23 '17 at 07:16

basic solution:

let set X be our output set.

for each number, n, between 1 and N:
    for each number, s, in set S:
        if s divides n:
            stop searching S, and move onto the next number,n.
        else if s is the last element in S:
            add n to the set X.

you can obviously remove multiples in S before running this algorithm, but I don't think prime numbers are the way to go

score 1 · Answer 3 · answered Dec 25 '17 at 06:15

Since S is sorted, we can guarantee O(N) complexity by skipping elements in S already marked (http://codepad.org/Joflhb7x):

N = 10
S = [2,4,5]
marked = set()
i = 0
curr = 1

while curr <= N:
  while curr < S[i]:
    print curr
    curr = curr + 1

  if not S[i] in marked:
    mult = S[i]

    while mult <= N:
      marked.add(mult)
      mult = mult + S[i]

  i = i + 1
  curr = curr + 1

  if i == len(S):
    while curr <= N:
      if curr not in marked:
        print curr
      curr = curr + 1

print list(marked)

Remove all the multiples of a given set of numbers from given range

3 Answers3