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

Question

致力于欧拉问题项目（26），并希望使用一种算法来查找素数p，最大阶为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

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 以使用一些智能幂。