使用 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（这也使它成为 sorted 的糟糕键）。请改用集合。

作为奖励，集合有一个删除元素的方法而不会引发异常，无论元素是否存在于集合中。

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

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 的影响（我在你的 "dictionaries" 函数中注释掉了 print 语句），也不受过多删除的影响，因为设置版本试图删除与你的字典版本相同的值做过。 set 版本有一个巨大的优势，因为它不需要 try-except 块来进行那些多余的删除。

我发现的第二大节省是使用 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

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

使用 python 中的字典筛选 eratosthenes

Sieve of eratosthenes using dictionaries in python

python

encryption

math