How do I efficiently find out how many numbers are not divisible from a list of primes?

Since the list contains distinct prime numbers, this problem can be reduced to finding how many numbers less than or equal to N are divisible by these primes then deduct that number from N.

Since N can be large (10^9) and K is not, you can use inclusion-exclusion principle to find that.

N/x = quantity of numbers less than or equal to N and are divisible by x

N/(x*y) = quantity of numbers less than or equal to N and are divisible by both x and y at the same time.

using inclusion exclusion principle and your sample data:

According to inclusion-exclusion, you add the number to the result when the

list_of_primes = [2, 3, 7]
n = 10

We add these:
10 / 2 = 5
10 / 3 = 3
10 / 7 = 1
-----------
         9
Subtract these:
10 / (2 * 3) = 1
10 / (2 * 7) = 0
10 / (3 * 7) = 0
----------------
               1
And add this:
10 / (2 * 3 * 7) = 0
--------------------
                   0

result = 9 - 1 + 0 = 8
n - result = 10 - 8 = 2 <-- this is the answer

You can implement that using a recursive approach as the following:

list_of_primes = [2, 3, 7]
n = 10
k = 3

def get_count(i, num, taken):
    if num > n:
        return 0
    if i == k:
        # the case 0 numbers taken
        if taken == 0:
            return 0
        # if odd number of numbers are taken
        if taken % 2:
            return n // num
        # if even number of numbers are taken
        return -1 * (n // num)
    return get_count(i+1, num * list_of_primes[i], taken+1) + get_count(i+1, num, taken)

print(n - get_count(0, 1, 0))
# 2

From wikipedia:

Generalizing the results of these examples gives the principle of inclusion–exclusion. To find the cardinality of the union of n sets:

1. Include the cardinalities of the sets.
2. Exclude the cardinalities of the pairwise intersections.
3. Include the cardinalities of the triple-wise intersections.
4. Exclude the cardinalities of the quadruple-wise intersections.
5. Include the cardinalities of the quintuple-wise intersections.
6. Continue, until the cardinality of the n-tuple-wise intersection is included (if n is odd) or excluded (n even).

It's very easy for your all_multiples_set to grow to a number very close to 10^9, which is going to consume on the order of 40GB of memory -- more than is reasonable on most machines! So you'll need a strategy that doesn't require you to keep track of so many numbers.

Start by getting N and K:

n, _ = map(int, input().split())
k = list(map(int, input().split()))

From there, one possible strategy would be to keep track of only the numbers that might actually match, and prune that number down as you go:

candidates = [c for c in range(1, n + 1) if c % k[0]]
for j in k[1:]:
    candidates = [c for c in candidates if c % j]

print(len(candidates))

This has the advantage of getting faster and smaller when you're going through a large K list, but it still has the space problem because you start off with a lot of candidates (e.g. if N is 10^9 and your first value of K is 2, you have 5 billion ints to keep track of, which is better than 10 billion but still too many).

The way to do this without taking up any space at all is to iterate through all the candidates from 1 to N, completely evaluate each one against each element of K, and add 1 to the count if it meets the criteria. That way the only thing you need to keep track of is the count, and not what all the actual numbers are.

print(sum(
    1 if all(c % j for j in k) else 0
    for c in range(1, n+1)
))

[Edited]

Be sure to convert to int before sorting: list_of_primes = list(map(int, input().split()))

I also found a way to optimize the code roughly 2x faster. Note that if in some branch num is multiplied by min prime number from list is larger then N, than there is no need to continue and branch more, since we wouldn't change num as it is already big enough. Therefore, the following code:

list_of_primes = [11, 13, 17, 19, 23, 29, 31, 37, 41,
                  43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
                  103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193]
n = 10 ** 9
list_of_primes.sort(reverse=True)
k = len(list_of_primes)
min_prime = list_of_primes[-1]


def get_count(i, num, taken):
    if num > n:
        return 0
    # if min_prime * num > n then we won't take any new numbers
    # thus taken won't change
    if min_prime * num > n or i == k:
        # the case 0 numbers taken
        if taken == 0:
            return 0
        # if odd number of numbers are taken
        if taken % 2:
            return n // num
        # if even number of numbers are taken
        return - 1 * (n // num)
    return get_count(i+1, num * list_of_primes[i], taken+1) + get_count(i+1, num, taken)


print(n - get_count(0, 1, 0))

is almost two times faster on the given test than the previous solution: 0.25s vs 0.63s.

Old solution:

I found a way to decrease the depth of the recursion. You should iterate through descending sorted array of prime numbers to faster finish branching, i.e.:

list_of_primes.sort(reversed=True)

Thus in the worst case I improved the time from 5 seconds to 1.2 seconds.

list_of_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
                  43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
                  103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173]
n = 10 ** 9
list_of_primes.sort(reverse=True)
k = len(list_of_primes)


def get_count(i, num, taken):
    if num > n:
        return 0
    if i == k:
        # the case 0 numbers taken
        if taken == 0:
            return 0
        # if odd number of numbers are taken
        if taken % 2:
            return n // num
        # if even number of numbers are taken
        return -1 * (n // num)
    return get_count(i+1, num * list_of_primes[i], taken+1) + get_count(i+1, num, taken)


print(n - get_count(0, 1, 0))