python - 在 python 中使用字典筛选 eratosthenes

Question

以下是埃拉托色尼筛法的两种形式。

---

1) 首先是我在观看可汗学院视频 (https://www.khanacademy.org/computing/computer-science/cryptography/comp-number-theory/v/sieve-of-eratosthenes-prime-adventure-part-4) 时解释如何对 Sieve 进行编程的方式，该算法使用模块化划分。

---

2) 我对第二个进行了一些修改以加快算法速度，包括:使用字典并从字典中删除复合元素使用乘法而不是模除法来查找复合元素来测试它们，然后在之后创建一个排序列表筛子完成了。

第二种方法要快得多，但我必须添加一个 try 语句，以避免函数尝试删除已经删除的值，但仍然删除元素的倍数的情况尚未删除。

问题是，有没有什么方法可以避免已经发现是复合的值，而不是使用 try 语句跳过它们，同时仍然使用乘法来定位复合值？

   def Sieve_2_b(b):
      seq_primes=list()
      c=0
      for i in range(2,(1+b)):
          seq_primes.append(i)
      while (seq_primes[c]**2)<b:
          k=c
          while k<(len(seq_primes)):
              if seq_primes[k]>=(seq_primes[c]**2):
                  if seq_primes[k]%seq_primes[c]==0:
                      del seq_primes[k]
                      k-=1
              k+=1
          c+=1
      return seq_primes

    def Sieve_2_b_using_dict(b):
        seq_primes=list()
        sieve_dict=dict()
        c=0
        for i in range(2,(1+b)):
            seq_primes.append(i)
            sieve_dict[i]=0
        while (seq_primes[c]**2)<b:
            k=c
            while seq_primes[k]<=(b/seq_primes[c]):
                try:
                    del(sieve_dict[(seq_primes[k]*seq_primes[c])])
                except:
                    print(seq_primes[k],seq_primes[c],'stop this')
                    pass
                k+=1
            c+=1
        seq_primes=sorted(sieve_dict,key=sieve_dict.get)
        return seq_primes

Answer 1

您的字典为每个键存储一个无用的值 --- 它总是 0(这也使它成为排序的糟糕键) .请改用集合。

作为奖励，无论元素是否存在于集合中，集合都有一种方法可以移除元素而不会引发异常。

这是我的第一个版本，大部分是从您的代码中复制和粘贴的:

def sieve_using_set(b):
    seq_primes=list(range(2, b + 1))
    sieve_set=set(range(2, b + 1))
    c=0
    while (seq_primes[c]**2)<b:
        k=c
        while seq_primes[k]<=(b/seq_primes[c]):
            sieve_set.discard(seq_primes[k] * seq_primes[c])
            k+=1
        c+=1
    return list(sorted(sieve_set))

它也快得多。速度不受 I/O 的影响(我在你的“字典”函数中注释掉了 print 语句)，也不受过多删除的影响，因为设置版本试图删除你的字典版本所做的相同值. set 版本有一个巨大的优势，因为它不需要 try-except block 来那些多余的删除。

我发现的第二大节省是使用 range 而不是不断地将 c 或 k 与某些计算进行比较。为此，我在文件顶部添加了一个import math:

def sieve_using_set_and_ranges(b):
    seq_primes=list(range(2, b + 1))
    sieve_set=set(range(2, b + 1))
    for c in range(0, math.floor(math.sqrt(b)) + 1):
        for k in range(c, math.floor(b / seq_primes[c]) + 1):
            sieve_set.discard(seq_primes[k] * seq_primes[c])
    return list(sorted(sieve_set))

下面是 timeit.Timer.timeit 在 1000 长筛子上运行 1000 次的结果，使用旧安装的 Python 3.1:

Sieve using modular division:
5.98897910118
Sieve using dictionary:
5.10295796394
Sieve using set:
3.10129499435
Sieve using set and ranges:
1.69016003609

我使用断言来证明集合版本产生了与您的两个函数相同的列表输出。