数学范围误差-是否有办法进一步限制该算法以避免
数学范围误差-是否有办法进一步限制该算法以避免
提问于 2015-04-10 11:49:12
研究项目Euler问题(26)，并希望使用一个算法来寻找最大阶为10模p的素数p。问题实质上是寻找在小数中产生最长重复的分母。在阅读了大量维基百科之后，上面描述的黄金似乎就能实现这一目标。但是，不幸的是，它似乎采取了非常大的力量，10的结果是一个错误。那么，我的问题是:是否有办法避免这一错误(使数字变小)，或者我是否应该放弃这一策略，只做长除法(计划是专注于素数)。值得注意的是，在order_ten方法中，如果我限制了10到300的幂，并且可能会长一点，我就可以让它运行，这与长的长度是一样的。
import math
def prime_seive(limit):
seive_list = [True]*limit
seive_list[0] = seive_list[1] = False
for i in range(2, limit):
if seive_list[i] == True :
n = 2
while i*n < limit :
seive_list[i*n] = False #get rid of multiples
n = n+1
prime_numbers = [i for i,j in enumerate(seive_list) if j == True]
return prime_numbers
def order_ten(n) :
for k in range(1, n) :
if (math.pow(10,k) -1)%n == 0:
return k
primes = prime_seive(1000)
max_order = 0
max_order_d = -1
for x in reversed(primes) :
order = order_ten(x)
if order > max_order :
max_order = order
max_order_d = x
print max_order
print max_order_d
回答 1
Stack Overflow用户
回答已采纳
发布于 2015-04-10 12:04:39
我怀疑问题是，当首先取10的大幂，然后计算mod n时，你的数字就会变大。(例如，如果我要求你计算10^11 mod 11，你可以说10 mod 11是(-1)，因此10^11 mod 11就是(-1)^11 mod 11 ie。-1.)
也许您可以尝试编写自己的指数例程mod n，类似于(在伪代码中)。
myPow (int k, int n) {
if (k==0) return 1;
else return ((myPow(k-1,n)*10)%n);
}这样，你就永远不会处理大于n的数字。用它的书写方式，就可以得到计算幂的线性复杂度，从而得到函数order_ten(n)在n中的二次复杂度。如果这太慢了，您可以改进函数myPow来使用一些智能指数。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29560707
复制相关文章
相似问题
腾讯云开发者
