問題97 - 歐拉項目：我的代碼出了什麼問題？

Question

我想從項目歐拉，使用python解決問題97。

目標是找到28433×2^7830457 + 1的最後10位數字，但我的解決方案似乎關閉了，而且我無法確定哪裏出了問題。

我想到了循環中的一個錯誤的錯誤，但添加或刪除一個仍然給出了錯誤的答案，無論如何，這似乎是邏輯上合理的。

有人可以幫助我嗎？

感謝

def PE97(): 
    mod = 10**10 
    base = 2 

    for i in range(7830456): 
     base = (base * base)%mod 

    print((28433*base+1)%mod) 

PE97() 

編輯：忽略此，我吸創造它似乎是一個POW（）函數。

Answer 1

這個片段：

for i in range(7830456): 
     base = (base * base)%mod 

不計算2^7830457。提升到2的冪，所以第一次運行之後，你有基礎= 4，則基地每個循環基地後= 8等

Answer 2

你的問題是在這裏

base = 2 
for i in range(7830456): 
    base = (base * base)%mod 

出現這種情況基地將在第一時間2^2然後它是2^4然後2^8 ... & c。

您需要重新考慮計算兩個冪的算法。

Answer 3

爲了清楚起見，我會指出python的內置pow是模塊化的指數。而且速度很快。

>>> pow(2, 5, 30) 
2 
>>> pow(2, 7830456, 6542) 
5778 
>>> timeit.timeit(stmt='pow(2, 5, 30)', number=100000) 
0.031174182891845703 
>>> timeit.timeit(stmt='pow(2, 7830456, 6542)', number=100000) 
0.11496400833129883 

我從你的編輯中無法分辨出你是否剛剛發現了這個問題，所以我想我會提及它。