3和5的整数倍数求和溢出

Question

我相信这个问题已经被问了很多，但我已经查过其他论坛，并试图解决这个问题，这似乎没有帮助。我在想有一个溢出问题，但我不记得该怎么解决它了。我花了很长一段时间来编写代码（我的错在这里），所以我正在尝试一些问题来帮助我重新回到正常的状态。所以，只是想知道到底出了什么问题。当我尝试n = 1000时，答案是错误的，但是小于这个数字的数字似乎是正确的。因为大数字行不通，我认为这是一个整数溢出。在

def n_number():
    n = raw_input("Enter a max number: ")
    try:
        int(n)
        return n

    except ValueError:
        print 'Value is not an integer'
        exit(1)

# 'function that will add multiples of 3 and 5 that are less than the given value, n.'
def sum_multiplies(n):
    sum = long(0)
    counter3, counter5 = int(1),int(1)

    value3 = 3*counter3
    value5 = 5*counter5

    while True:
        # 'sums of multiples of 5\'s less than n'
        if value5<int(n):
            sum+= value5
            counter5+=1
            value5 = 5*counter5

        # 'sums of multiples of 3\'s less than n'
        if value3<int(n):
            sum+= value3
            counter3+=1
            value3 = 3*counter3

        else:
            break

    print "sum: %s" %sum
    print "counter3: %s" %counter3
    print "counter5: %s" %counter5

def main():
    'max number is in n'
    n = n_number()

    sum_multiplies(n)

if __name__ == "__main__":
    main()

Answer 1

看起来你在重复计算15的倍数。在

Answer 2

您当前正在O(n)时间内执行此操作-您可以在恒定时间内完成！在

' sum values from 1 to m'
def unitSum(m):
    return (m * (m + 1)) / 2

def sum_multiplies(n):
    threes = int(n / 3)
    fives = int(n / 5)
    fifteens = int(n / 15)
    threesum = unitSum(threes) * 3
    fivesum = unitSum(fives) * 5
    fifteensum = unitSum(fifteens) * 15
    return threesum + fivesum - fifteensum

你得原谅我对python知识的缺乏，我是一个java人。可能有一些偶然的语法错误。但这里的想法是，以n = 40为例，您将3 5 6 9 10 12 15 18 20 21 24 25 27 30 33 35 36 39 40相加。这和3 6 9 12 15 18 21 24 27 30 33 36 39 UNION 5 10 15 20 25 30 35 40是一样的，现在认识到3 6 9 12 ...和{}是一样的，我们可以用“单位和”（1 2 3 4）到项的数目，即n / mult，然后用这个和乘以mult，就像我们对3 * (1 2 3 4)所做的一样。好消息是单位和可以在恒定时间内计算出来，因为n * (n + 1)唯一的问题是15的倍数会出现两次（同时在5s和3s中计算），所以我们也必须将它们减去。在

Answer 3

问题是你把3和5（比如15）的倍数数两次。在

解决这个问题的一种方法是添加：

if counter3%5 == 0: continue

跳过重复计算。在