python - 小于最大数的倍数

Question

对于SingPath的以下问题:

Given an input of a list of numbers and a high number, 
return the number of multiples of each of 
those numbers that are less than the maximum number.
For this case the list will contain a maximum of 3 numbers 
that are all relatively prime to each
other.

这是我的代码:

def countMultiples(l, max_num):
    counting_list = []
    for i in l:
        for j in range(1, max_num):
            if (i * j < max_num) and (i * j) not in counting_list:
                counting_list.append(i * j)
    return len(counting_list)

虽然我的算法工作正常，但当最大数太大时它会卡住

>>> countMultiples([3],30)
9      #WORKS GOOD

>>> countMultiples([3,5],100)
46     #WORKS GOOD

>>> countMultiples([13,25],100250)
Line 5: TimeLimitError: Program exceeded run time limit. 

如何优化这段代码？

Answer 1

3 和 5 有一些相同的倍数，比如 15。

你应该删除那些倍数，你会得到正确的答案

还应该检查包含排除原则https://en.wikipedia.org/wiki/Inclusion-exclusion_principle#Counting_integers

编辑:这个问题可以在常数时间内解决。如前所述，解决方案是包含 - 排除原则。

假设你想得到小于 100 的 3 的倍数，你可以通过除以 floor(100/3) 来实现，这同样适用于 5，floor(100/5)。现在要获得小于 100 的 3 和 5 的乘积，您必须将它们相加，然后减去两者的倍数。在这种情况下，减去 15 的倍数。因此，小于 100 的 3 和 5 的倍数的答案是 floor(100/3) + floor(100/5) - floor(100/15)。如果你有超过 2 个数字，它会变得有点复杂，但同样的方法适用，更多检查 https://en.wikipedia.org/wiki/Inclusion-exclusion_principle#Counting_integers

编辑2:

循环变体也可以加速。您当前的算法在列表中附加多个，这非常慢。您应该切换内部和外部 for 循环。通过这样做，您将检查是否有任何除数除以该数字，然后您得到除数。

因此只需添加一个 bool 变量，它会告诉您是否有任何除数除以该数字，并计算该变量为真的次数。

所以它会像这样:

def countMultiples(l, max_num):
  nums = 0
  for j in range(1, max_num):
    isMultiple = False
    for i in l:  
      if (j % i == 0):
    isMultiple = True
    if (isMultiple == True):
      nums += 1
  return nums

print countMultiples([13,25],100250)