我对埃拉托斯提尼的筛子的执行有缺陷吗？

Question

我正在筛选Python中的Eratosthenes实现。问题是并不是所有的素数都出现了（主要是编号较低的素数）。在

这是我的代码：

def prevPrimes(n):
    from math import sqrt
    from time import time
    start = time()
    if type(n) != int and type(n) != long:
        raise TypeError("Arg (n) must be of <type 'int'> or <type 'long'>")
    if n <= 2:
        raise ValueError("Arg (n) must be at least 2")
    limit, x, num, primes = sqrt(n), 2, {}, []
    for i in range(1, n+1):
        num[i] = True
    while x < limit:
        for i in num:
            if i%x==0:
                num[i] = False
        x += 1
    for i in num:
        if num[i]:
            primes.append(i)
    end = time()
    primes = sorted(primes)
    print round((end - start), 2), ' seconds'
    return primes

如果我输入>>> prevPrimes(1000)，我希望结果以：[2, 3, 5, 7, 11, 13, 17]等开头。但是，它看起来是这样的：[1, 37, 41, 43, 47, #more numbers]。在

我知道问题在于它将“原始”素数（2、3、5、7、11、13、17等）声明为False，因为我的程序检查这些素数的方式。我怎样才能避免这种情况？提前感谢：）

Answer 1

首先，你具体问题的答案。你正在丢弃小于n平方根的素数。最简单的修复方法是在内部循环的末尾将num[i] = False更改为num[i] = (not x == i)（我认为这是可行的，我还没有测试过）。在

第二，你的算法是试除法，而不是埃拉托什尼的筛子，它的时间复杂度是O（n2）而不是O（logloglogn）。模运算符给出了博弈结果。最简单的Eratosthenes筛选如下（伪代码，可以将其翻译为Python）：

function primes(n)
  sieve := makeArray(2..n, True)
  for p from 2 to n step 1
    output p
    for i from p+p to n step p
      sieve[i] := False

有一些方法可以改进这种算法。如果您对使用质数编程感兴趣，我谦虚地推荐this essay，它包括一个优化的Eratosthenes筛选，并用Python实现。在

Answer 2

所以这并不是一个实际的SoE实现，下面是我不久前写的。在

number_primes = 10
prime_list = [True]*number_primes

for i in range (2, number_primes):    #check from 2 upwards
  if prime_list[i]:                   #If not prime, don't need to bother about searching
    j = 2
    while j*i < number_primes:        # Filter out all factors of i (2...n * prime)
      prime_list[j*i] = False
      j+=1

Answer 3

有时当你迭代num，x等于i，因此i % x等于0，并且{}被标记为非素数。在

您需要在while循环中的某个地方添加if not x == i:，例如：

while x < limit:
        for i in num:
            if not x == i:
                if num[i] and i%x==0:
                    num[i] = False