2

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

但是，当我运行它时，试用分区要快得多。例如， when 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
4

3 回答 3

2

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

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

如果做得好，is_prime_sieve就变成了简单的：

def is_prime_sieve(n):
    return prime[n]

你不需要while循环。

于 2015-06-05T16:56:21.470 回答
1

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

这就像比较公共汽车和两座跑车的速度。如果您需要将 50 个人从 A 带到 B，那么公共汽车会快得多。如果您乘坐一个乘客，猜猜看，跑车会更快。

于 2016-06-26T13:31:21.833 回答
0

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

于 2019-06-24T20:34:15.073 回答