首先需要注意的是你写的并不是埃拉托色尼筛选法。看看一个完全天真的埃拉托色尼筛选法执行了多少次循环:
def sieve1(n):
loops = 0
numbers = set(range(2, n))
for i in range(2, int(n ** 0.5) + 1):
for j in range(i * 2, n, i):
numbers.discard(j)
loops += 1
return sorted(numbers), loops
测试过:
>>> sieve1(100)
([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97],
178)
对于100个数字,执行178次循环(不包括排序)。这可以通过一些微小的改变来改进:
def sieve2(n):
loops = 0
numbers = range(0, n)
for prime in numbers:
if prime < 2:
continue
elif prime > n ** 0.5:
break
for i in range(prime ** 2, n, prime):
numbers[i] = 0
loops += 1
return [x for x in numbers if x > 1], loops
测试过:
>>> sieve2(100)
([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97],
102)
对于100个数字,执行了102次循环(不包括最后的筛选操作)。现在看看你的代码:
def sieve3(n):
loops = 0
numbers = range(2, n)
for i in numbers:
for j in numbers:
if j != i and j % i == 0:
numbers.remove(j)
loops += 1
return numbers, loops
测试过:
>>> sieve3(100)
([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97],
663)
情况变得更糟:
>>> [sieve1(x)[1] for x in [100, 1000, 10000]]
[178, 2978, 41723]
>>> [sieve2(x)[1] for x in [100, 1000, 10000]]
[102, 1409, 16979]
>>> [sieve3(x)[1] for x in [100, 1000, 10000]]
[663, 28986, 1523699]
当 n = 10000
时,你的实现所做的工作量几乎是原来的100倍!
我的建议是,在将代码变得“简洁”之前先创建一个合理的实现。代码高尔夫可能很有趣,但不管长度如何,写出 高效 的代码才是真正具有挑战性和启迪性的。
话虽如此,考虑一下这个一行代码(如果不算导入部分的话,可以使用 lambda x, y: x - y
替换 operator.sub
来消除导入)。这个实现了第一个算法并进行了小小的改进:
>>> from operator import sub
>>> reduce(sub, (set(range(x ** 2, 100, x)) for x in range(2, int(100 ** 0.5) + 1)), set(range(2, 100)))
set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97])