Trial Division 比 Sieve 更快进行素数测试？

Question

我在 python 中写了两个素数测试。第一个是基于试分法，第二个是埃拉托色尼筛法。我的理解是 sieve 的时间复杂度应该比 trial 小，所以 sieve 应该渐近地更快。

可是我运行它的时候，试分就快多了。例如，当 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

Answer 1

对于 Erastothenes 筛法，您每次都在重新计算筛法。应该缓存筛子，以便您只生成一次。当您构建一次筛子然后执行 many 素数检查时，它会很好地工作；如果只检查一个数字，效率很低。

顺便说一句，这意味着您需要预测最高素数并生成筛 table 直至该数。

如果操作正确，is_prime_sieve 将变得简单：

def is_prime_sieve(n):
    return prime[n]

您不需要 while 循环。

Answer 2

筛子从 1 到 n 找到所有个素数。计算 one 筛比对每个数字进行试验除法要快得多。显然，如果你从1到n确定所有个素数，然后丢掉前n-1个数的所有信息，那是非常低效的。

这就像比较公共汽车和双座跑车的速度。如果你需要载五十人从 A 到 B，公共汽车要快得多。如果你只载一个乘客，你猜怎么着，跑车更快。

Answer 3

但即使使用传统的构建筛子的方法，仍然会发生太多的交易。我开发了一种不除法提取质数的方法（数据管理目的除外），该方法适用于 Eratosthenes 的基本筛法。我不必设置任何上限或下限，该算法是完全开放式的。我开发了一个数据字符串，我可以从中转到计算范围内的任何地方，并提取子集范围内的所有质数。我用除法不浪费计算。

Trial Division 比 Sieve 更快进行素数测试？

Trial Division faster than Sieve for Primality Test?

python

primality-test