小于最大数量的倍数

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.

这是我的代码：

^{pr2}$

虽然我的算法工作得很好，但当最大值太大时，它会卡住

>>> 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的倍数。 所以3和5的倍数小于100的答案是floor（100/3）+floor（100/5）-floor（100/15）。 如果你有两个以上的数字，它会变得更复杂一些，但是同样的方法也适用于更多的check https://en.wikipedia.org/wiki/Inclusion-exclusion_principle#Counting_integers

编辑2：

也可以加速循环变量。 您当前的算法在列表中追加多个，这是非常慢的。 您应该切换内部和外部for循环。通过这样做，你可以检查是否有除数除以这个数，你就得到了除数。在

所以只要加上一个布尔变量，它告诉你是否有除数除以这个数，然后计算变量为真的次数。在

所以它会这样：

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)

Answer 2

如果列表的长度是您所需要的，那么最好使用一个计数，而不是创建另一个列表。在

def countMultiples(l, max_num):
    count = 0
    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:
                count += 1
    return count