python - 我如何有效地找出有多少数字不能从素数列表中整除？

Question

我是 python 的新手，为了学习我正在尝试解决一个问题作为练习。

N 是 [1, 10^9] 之间的整数 K 是长度 <= 40 的随机不同素数的列表，这些素数都等于或小于 N。

我的代码必须找到 <= N 且不能被列表 K 中的任何数字整除的数字的数量。

我写了下面的代码:

first_line = input().split()
second_line = input().split()


n = int(first_line[0])
list_of_primes = second_line

all_multiples_set = set()

for i in range(len(list_of_primes)):
    prime = int(list_of_primes[i])

    # Creates a set of all multiples numbers of this prime that are equal or less than N.
    one_multiple_set = set(range(prime ,n if n % prime  != 0 else n + prime ,prime ))

    # Makes a Union of this set with the previous sets of multiples, thus getting all multiples of a and b. 
    all_multiples_set = all_multiples_set.union(one_multiple_set)

print(n - len(all_multiples_set))

第一个输入由 2 个数字组成:分别是 N 和 K 的长度。 (即“10 3”)。

第二个输入是一系列长度小于或等于 N 的 K 个素数(即“2 3 7”)。

输出应该是一个整数，表示不能被列表 K 中的任何数字整除的等于或小于 N 的数字的数量。(即本例中的“2”)

我知道我的代码适用于某些情况，但不幸的是 platform where I found this puzzle没有告诉我我的代码在哪些情况下不起作用，它只告诉我它在某些情况下不起作用。

我相信这是一个内存问题。鉴于 10^9 是一个非常大的数字，但它也可能是我没有看到的错误。

我将不胜感激有关如何改进我的代码的指导或更好方法的建议。值得注意的是，由于这是一个练习，我无法导入模块，而且由于我正在尝试学习，我希望能解释为什么我的代码效率低下。

编辑:

执行时间也是一个因素。该代码的最大运行时间为 1 秒。

在我第一次尝试时，我写了这段代码:

linha1 = input().split()
linha2 = input().split()


n = int(linha1[0])
s = linha2



x = len(s)

value_to_add = 0
value_to_subtract = 0


for i in range(1 << x):

    single_set = []
    multiply = 1

    for j in range(x):
        if i & (1 << j):
            single_set.append(int(s[j]))

    for num in single_set:
        multiply *= num
        if multiply > n:
            break

    if len(single_set) == 1:
        value_to_add += n//single_set[0]

    elif len(single_set) > 1:
        value_to_subtract += n//multiply

print(n - value_to_add + value_to_subtract)

它也得到了正确的答案，但它需要很长时间才能运行。

Answer 1

由于列表包含不同的质数，这个问题可以简化为找出有多少个数小于或等于 N可以被这些素数整除然后从 N 中减去该数.

自 N可以很大 (10^9) 和 K不是，你可以用inclusion-exclusion principle找到那个。

N/x = 小于或等于 N 的数字数量并且可以被 x 整除

N/(x*y) = 小于或等于 N 的数字数量并且可以被 x 整除和 y同时。

使用包含排除原则和您的示例数据:

根据包含 - 排除，您将数字添加到结果中

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

您可以使用递归方法实现它，如下所示:

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

来自维基百科:

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