问题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 

我从你的编辑中无法分辨出你是否刚刚发现了这个问题，所以我想我会提及它。