python - 原始性测试的审判部门比Sieve更快？

我用python编写了两个素数测试。第一个基于试验划分，第二个基于Eratosthenes筛子。我的理解是，筛子的时间复杂度应小于试验，因此筛子的渐近速度应更快。

但是，当我运行它时，审判部门要快得多。例如，当n = 6*(10**11)时，is_prime(n)花费不到一秒钟的时间，但是is_prime_sieve(n)实际上永远不会结束！我把筛子写错了吗？

我的代码是：

# determines if prime using trial division
def is_prime(n):
    d = {}
    u = math.floor(math.sqrt(n))
    i = 2
    # trial division: works pretty well for determining 600 billion
    while (i <= u):
        if (n % i == 0):
            return False
        i += 1
    return True

# primality test with sieve
def is_prime_sieve(n):
    # first find all prime numbers from 2 to u
    # then test them
    u = math.floor(math.sqrt(n))
    prime = {}
    lst = range(2, int(u)+1)
    for i in lst:
        j = 2
        prime[i] = True
        while (i*j <= u):
            prime[i*j] = False
            j += 1
    while (u >= 2):
        if (u not in prime) or (prime[u]):
            if (n % u == 0):
                return False
        u -= 1
    return True

最佳答案

对于Erastothenes筛，您每次都在重新计算筛。筛子应被缓存，以便您只生成一次。当您先构建筛子然后执行许多原始性检查时，它会很好地工作。如果仅检查一个数字，则效率很低。

顺便说一句，这意味着您需要预料到最高质数并生成直到该质数的筛表。

正确完成后，is_prime_sieve变为：

def is_prime_sieve(n):
    return prime[n]

您不需要while循环。

关于python - 原始性测试的审判部门比Sieve更快？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30671876/