python - 素数测试比蛮力法花费的时间更长，我该如何改进？

Question

我正在尝试在一台机器上计算素数，大小约为 2^30-2^100。
我的算法包含在下面，供任何感兴趣的人使用。
我已将此 Python 代码优化为每个数字的 O(sqrt(n/2))(我相信):它只接受奇数，并且我确保传递给它的数字是奇数另一种方法。

我使用了费马素数检验来尝试加快这个过程。但是，对于内置的 math.pow() 方法来说，数字太大了，所以我使用了 Exponentiation by Squaring。
但是，对于较大的数字，这会花费很长时间——仅使用蛮力会更快。

我的实现有误吗？
时间来自平方算法，它的递归堆栈也占用了我的内存，有没有更快的算法我应该研究一下？

要计算数字 35184372088967 是否为质数，使用我的强力算法需要 .00100111 秒，但运行质数测试需要 .40608 秒。

暴力素数检查:

def isPrime(n):
    for i in range(3,int(math.sqrt(n)),2):
        if(n%i==0):
            return False
    return True

费马算法的实现:

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)

Answer 1

错误:math.pow 计算浮点值。浮点计算是近似的，在这里会给你无意义的结果。您需要整数计算，例如您在 power 函数中所做的(效率低下)。 Python 的内置 ** 运算符和 pow 函数(不是 math.pow，这是一个不同的函数)都对整数进行运算。

在 Python 中，就像在许多编程语言中一样，名为 math 的库专门用于浮点计算，而不是关于其他类型的数学计算，例如对整数进行的计算。

效率低下:要计算 b^e mod n，执行算术模 n 比先计算 b^e 然后将结果除以 n 效率要高得多。计算 b^e 需要建立一个非常大的数字，这会很慢，因为随着计算 b 的幂越来越大，数字会很快变大。 (计算 b^e 的最佳方法不容易确定，但所有方法都涉及计算 b 的中间幂，唯一实际不确定的是顺序。)当你想要结果模 n 时，做所有连续的乘法模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 的幂，有一种比乘法快得多的方法 — bit shifting .但这在这里没有帮助，因为您想计算 2^e mod n 而不是 2^e。