我正在經(jīng)歷歐拉項目,和很多人一樣,我陷入了效率的困境。我不介意嘗試將時間從 7 毫秒減少到 6 毫秒,但我確實關(guān)心循環(huán)必須等待半個小時。問題是:能被 1 到 20 中所有數(shù)字整除的最小正數(shù)是多少?我認為我在 python 中有一個有效的解決方案,但效率非常低。import sysimport mathdef multiple(): multiple = 20 multiples = [] while multiple < math.sqrt(sys.maxsize): div_flag = False max_flag = False for i in range(2, 21): if multiple % i == 0: div_flag = True if i == 20: max_flag = True else: max_flag = False if multiple % i != 0: div_flag = False break if max_flag == True: multiples.append(multiple) multiple = math.sqrt(sys.maxsize) multiple += 20 print(multiple, "div_flag: " + str(div_flag), "max_flag: " + str(max_flag), str(multiples)) # These prints are just there for debugging. print(multiples)multiple()正如您所看到的,它循環(huán)遍歷每個數(shù)字,直到最大安全整數(shù)的 sqrt() 為止。原因是sqrt()因為我試圖讓它更有效率,但無論如何它從未達到這一點。我讓它運行了大約 15 分鐘,數(shù)量達到了 200 萬左右(這是當變量multiples為 2 并增加 1 時的情況)。然后,我嘗試增加multiple變量 20(如上所示),在 15 分鐘多一點的時間里,我得到了 4500 萬。我在做project euler的時候看了一下答案,大概是2億左右。我沒有作弊,我只是確保我的程序有問題,并且沒有跳過那個目標數(shù)字。我說,怎樣才能讓我在一分鐘之內(nèi)得到答案。正如我所說,我不是一個效率狂,我只是想在一分鐘內(nèi)看到結(jié)果。我對 python 相當陌生,所以我知道有一些非常明顯的答案。PS我不喜歡直接重寫我的代碼,所以也許這里和那里有一些示例代碼,以及一些提示會很好。(所以我實際上學習并改進了我的編碼。)
1 回答

慕俠2389804
TA貢獻1719條經(jīng)驗 獲得超6個贊
我不熟悉歐拉項目,但這個問題實際上并不是一個編程問題,而是一個數(shù)學問題。答案就是2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19。
如果您嘗試查看從 1 開始的每個數(shù)字,直到找到符合標準的數(shù)字,那么您就錯誤地解決了問題。
您的目標是計算lcm(1, 2, 3, 4, .... 20)
最小公倍數(shù)。stackoverflow 上的一些搜索將向您展示如何計算數(shù)字列表的 lcm。有趣的是,它將被添加到 Python 3.9 中。math.lcm
添加回答
舉報
0/150
提交
取消