我正试图在一台机器上计算素数，大小约为2^30-2^100。
下面为感兴趣的人提供了我的算法
我已经将这个Python代码优化为每个数字的O(sqrt(n/2))(我相信)：它只接受奇数，并且我确保在另一种方法中传递给它的数字是奇数。
我使用Fermat素性测试来尝试加快这个过程。但是，对于内置的math.pow()方法来说，这些数字太大了，所以我使用了平方幂
然而，对于较大的数字来说，这需要很长时间——只使用蛮力会更快。
我的实现是错误的吗
时间来自平方算法，它的递归堆栈也占用了我的内存，有没有更快的算法我应该研究？
要计算数字35184372088967是否为素数，使用我的强力算法需要00100111秒，但运行素数测试需要.40608秒。
Brute force素数检查：
def isPrime(n):
for i in range(3,int(math.sqrt(n)),2):
if(n%i==0):
return False
return True
Fermat算法的实现：
def couldBePrime(n):
if(n>308):
return power(2,n-1)%n==1
else:
return math.pow(2,n-1)%n==1
平方幂算法(耗时部分)：
def power(base,exp):
if exp == 0:
return 1
elif exp == 1:
return base
elif (exp & 1) != 0:
return base * power(base * base, exp // 2)
else:
return power(base * base, exp // 2)
Bug：math.pow计算浮点值。浮点计算是近似的，在这里会给你带来毫无意义的结果。您需要整数计算，就像您在power函数中所做的那样(效率低下)。Python内置的**运算符和pow函数(不是math.pow，后者是一个不同的函数)都对整数进行运算。
在Python中，与许多编程语言一样，名为math的库专门用于浮点计算，而不是其他类型的数学计算，如对整数的计算。
效率低下：要计算b^e mod n，执行模n运算要高效得多，而不是先计算b^e，然后将结果除以n，这将是缓慢的，因为随着计算经过越来越高的b的幂，数字会很快变大，对模n进行所有连续乘法运算：计算b^2 mod n，然后平方并减少模n，得到b^4 mod n等。每次进行乘法运算时，在进行其他操作之前，先取除以n的余数。
在Python中，标准库函数pow(请记住，而不是math.pow)将为您执行此操作。它就像一样简单
def couldBePrime(n):
return pow(2, n-1, n) == 1
如果Python没有这个函数，那么power函数是实现它的合理方法，如果你减少了每个中间结果的模n。
def power(base, exp, mod):
if exp == 0:
return 1
elif exp == 1:
return base % mod
elif (exp & 1) != 0:
return (base * power((base * base) % mod, exp // 2, mod)) % mod
else:
return power((base * base) % mod, exp // 2)
当然，调用内置函数要快得多，这既是因为这是一种不错但不太好的执行操作的方式，也是因为Python在易写性方面比在速度方面更优化，所以最好将尽可能多的数字繁重留给内置函数。
另外要注意的是：要计算2的幂，有一种比乘法快得多的方法——移位。但这在这里没有帮助，因为你想计算2^e mod n，而不是2^e。