整数溢出3和5的倍数

我相信这个问题已经被问了很多，但我已经检查过其他论坛，并试图解决这个问题，这似乎没有帮助。我认为有一个溢出问题，但我不记得如何解决它。我花了很长时间从编码中解脱出来（我的错在那里），所以我正在尝试一些问题来帮助我摆脱困境。所以，只是想知道哪里出了问题。当我尝试n = 1000的答案是错误的，但数字小于这似乎是正确的。由于大数字不会工作，我认为这是一个整数溢出。整数溢出3和5的倍数

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

来源

2012-07-27 zyeek

你不能在Python溢出'int's，它们是任意精度的（模仿Python 2中的'long'实现细节，以及像range这样的疯狂内建函数实际上会抛出'OverflowError'，因为它们只能执行C'double'）。 – Julian 2012-07-27 20:52:45

溢出没有问题，使用mod（'％'）运算符来确定给定的数字是否可被其他整数所整除。例如。 'n％3 == 0'表示'n'能被3等整除 – Levon 2012-07-27 20:53:02

这可以简单得多：'sum（（x for x in range（1000）if x％3 == 0 or x％5 == 0））' – mgilson 2012-07-27 20:53:42

问题是你计算的数字是3和5（如15）的倍数两倍。

一个解决这个问题的办法是补充：

if counter3%5 == 0: continue

跳过重复计算。

来源

2012-07-27 20:53:26

啊好的。我现在完全明白了。不知道为什么我甚至懒得想到这一点。谢谢 – zyeek 2012-07-27 20:55:32

看起来你是重复计算的15

来源

2012-07-27 20:54:20

你目前正在做这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 ...与3 * (1 2 3 4...)相同，并且与五个相同，我们可以将“单位总和”（1 2 3 4）增加到术语数n/mult，并将该总和乘以mult，正如我们对3 * (1 2 3 4)所做的那样。好消息是单位总数可以在不变的时间内计算出来，如n * (n + 1)唯一的一个问题是，15的倍数将在那里两次（在5s和3s中计数），所以我们必须减去它们也是如此。

来源

2012-07-27 21:05:08 corsiKa

是的，谢谢。我只是懒惰地查找公式，找出从1到x的给定范围值的总和公式。请记住，从我的具体数学课上。我只是试图在我的python上练习。此外，感谢您提醒我总是寻找一种更好的方式来完成优化工作。在我刚刚阅读的python中，我可以做这个总和（[i in for i in range（1,1000）if i％3 == 0 or i％5 == 0]），但我很漂亮确定这是一个O（n） – zyeek 2012-07-27 21:09:39

它是'O（n）' - 我相信我在该代码中有一个小错误，但是这个想法存在 – corsiKa 2012-07-27 21:16:53

看起来我没有错误，除了'/2'错误，我以前省略。下面是它的一个样例运行：http://ideone.com/YQ4M4 – corsiKa 2012-07-27 21:20:49

它应该是非常快，非常可读，并且可以在CPython 2.x和3.x上运行。我已经＃！'它pypy，但这并非是必然的。需要注意的是范围（）是2.x的渴望，对3.X懒：

#!/usr/local/pypy-1.9/bin/pypy 

divisible_by_3 = set(range(0, 1000, 3)) 
divisible_by_5 = set(range(0, 1000, 5)) 

divisible_by_either = divisible_by_3 | divisible_by_5 

print(sum(divisible_by_either))

来源

2012-07-27 21:31:09 user1277476

使用生成器表达式，这里是一个一行

result = sum(num for num in xrange(1000) if (num % 5 ==0) or (num % 3 == 0))

来源

2012-07-27 21:34:30 gsk

整数溢出3和5的倍数

回答

相关问题