小编CS2*_*016的帖子

我试图在一台机器上计算素数,大小约为2 ^ 30-2 ^ 100.
对于任何感兴趣的人,我的算法都包含在
我已经针对O(sqrt(n/2))每个数字优化了这个Python代码(我相信):它只接受奇数,并且我确保传递给它的数字在另一个方法中是奇数.

我使用费马素性测试来尝试加快这个过程.但是,对于内置math.pow()方法,数字太大,所以我使用了Squaring的Exponentiation.
然而,对于更大的数字来说这需要很长时间 - 使用蛮力会更快.

我的实施错了吗？
时间来自平方算法,它的重复堆栈也占用了我的记忆,我应该研究一个更快的算法吗？

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

蛮力素数检查:

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)