整數溢出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的倍數

回答

相關問題