数学范围错误 - 有没有办法进一步限制此算法以避免

Question

正在研究项目 Euler 问题 (26)，并希望使用一种算法寻找最大阶为 10 模 p 的素数 p。本质上，问题是寻找在小数中创建最长重复的分母。在阅读了一堆维基百科之后，看起来上面描述的素数可以满足这个要求。但是，不幸的是，看起来采用 10 的非常大的幂会导致错误。那么我的问题是：有没有办法解决这个错误（使数字变小），或者我应该放弃这个策略而只做长除法（计划是专注于素数）。 [值得注意的是，在 order_ten 方法中，如果我将 10 的幂限制为 300，我可以得到运行并且可能会有点长，这与 long 的长度一致]

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

Answer 1

我怀疑问题是当首先取 10 的大次方然后计算值 mod n 时，你的数字变大了。（例如，如果我让你计算 10^11 mod 11，你可以说 10 mod 11 是 (-1)，因此 10^11 mod 11 只是 (- 1)^11 mod 11 即 -1.)

也许你可以尝试编写自己的求幂例程 mod n，类似于（伪代码）

myPow (int k, int n) {
   if (k==0) return 1;
   else return ((myPow(k-1,n)*10)%n);
}

这样你就永远不会处理大于 n 的数字。按照它的编写方式，您将获得 k 的线性复杂度来计算幂，因此函数 order_ten(n) 的 n 的二次复杂度。如果这对您来说太慢，您可以改进函数 myPow 以使用一些智能取幂。

数学范围错误 - 有没有办法进一步限制此算法以避免

math range error - is there a way to further limit this algorithm to avoid

algorithm

math

primes