Python:添加查找预生成列表后,isPrime函数要慢得多吗？

Question

我正在使用Python解决Project Euler问题.我已经看到一些求解器使用的isPrime()函数只是测试是否x % y == 0所有y 2 to x ** 0.5.这样效率不高,我希望isPrime()根据num % 30测试编写更好的功能.这就是我想出的:

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
primality = [1, 7, 11, 13, 17, 19, 23, 29]

def isPrime(num):
    if not type(num) in (int, long):
        raise ValueError
    if num in primes:
        return True
    elif num < 2:
        return False
    elif num % 30 not in primality:
        return False
    else:
        for prime in primes[3:]:
            if num % prime == 0:
                return False
        seed, sqrt, tryfactor = 1, getIntSquareRoot(num), 1
        while tryfactor < sqrt:
            for trymod in primality:
                tryfactor = seed * 30 + trymod
                if num % tryfactor == 0 and not(num == tryfactor):
                    return False
            seed += 1
        return True

问题7是找到第10001个素数.所以我决定让代码将所有这些素数附加到后续问题可以引用的列表中.我认为给定一个5位数的数字num,num in primes将是一个更快的重复操作num % tryfactor.对于从列表中primes[-1] < num < (primes[-1] ** 0.2)获取tryfactor值而不是重复生成它们的速度应该更快的参数tryfactor = seed * 30 + trymod.

所以我想出了以下内容:

def problem7():
    count, seed = len(primes), 1
    while True:
        for modulus in primality:
            num = seed * 30 + modulus
            if isPrime(num):
                count += 1
                primes.append(num)
                if count > 10000:
                    return num
        seed += 1

def isPrimeB(num):
    if not type(num) in (int, long):
        raise ValueError
    if num in primes:
        return True
    elif num < 2:
        return False
    elif num % 30 not in primality:
        return False
    else:
        for prime in primes[3:]:
            if num % prime == 0:
                return False
        seed, sqrt, tryfactor = 1, getIntSquareRoot(num), 1
        while tryfactor < sqrt:
            for trymod in primality:
                tryfactor = seed * 30 + trymod
                if num % tryfactor == 0 and not(num == tryfactor):
                    return False
            seed += 1
        return True

当然我希望问题7的代码要慢得多,因为生成素数列表几秒钟.我还期望稍后调用的问题isPrime()(例如10,27,35,41和58)的代码运行得更快.

然而,当问题27,35,41和58的代码变得慢得多时,我感到震惊.有人可以解释为什么在列表中查找值比计算它们要慢得多吗？或者我的代码中有错误吗？我还能做些什么来提高isPrime()功能效率？

Answer 1

它较慢的原因是因为列表查找是O(n).而不是使用列表使用集:

primes = set()
primes.add(num)

该num in primes检查现在是O(1).

也忘了这个"优化":primes[3:].它实际上会降低代码的速度,因为它会重新创建列表(请注意,如果切换到集合,它将无法正常工作).

最后,你可以实现Eratosthenes的Sieve(尽管有更复杂的筛子)来快速生成质数.