0

我正在用 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因为我的程序检查素数的方式。我怎样才能避免这种情况？提前致谢 ：）

4

4 回答 4

1

First, the answer to your specific question. You are discarding the primes less than the square root of n. The easiest fix is to change the line num[i] = False to num[i] = (not x == i) at the end of your inner loop (I think that works, I haven't tested it).

Second, your algorithm is trial division, not the Sieve of Eratosthenes, and will have time complexity O(n^2) instead of O(n log log n). The modulo operator gives the game away. The simplest Sieve of Eratosthenes looks like this (pseudocode, which you can translate into 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

There are ways to improve that algorithm. If you're interested in programming with prime numbers, I modestly recommend this essay, which includes an optimized Sieve of Eratosthenes with implementation in Python.

于 2012-11-21T15:24:56.030 回答
1

有时，当您遍历 时num，x等于i，因此i % x等于 0，i并被标记为非质数。

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

while x < limit:
        for i in num:
            if not x == i:
                if num[i] and i%x==0:
                    num[i] = False
于 2012-11-21T05:36:53.130 回答
1

所以这不是一个实际的 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
于 2012-11-21T06:54:57.297 回答
0

进口时间

def primes_sieve1():

limitn = int(raw_input("Please enter an upper limit ")) +1
start = time.clock()
primes = {
    }

for i in range(2, limitn):
    primes[i] = True

for i in primes:
    factors = range(i,limitn, i)
    for f in factors[1:]:
        primes[f] = False

end = time.clock()
print "This took ",end-start," seconds"
return [i for i in primes if primes[i]==True]

primes_sieve1()

这段代码不使用除法，而是取所有小于极限根的数字的倍数，并将它们更改为 false。这有点快，因为它不涉及将每个数字除以其他数字。

同样低于 1000 的情况会发生，即素数将被自身模数为 0，因此程序会认为它是错误的。由于 sqrt(1000) 大约是 31，因此小于 31 的素数会受到影响。

例如，在“while x < limit”的第 7 次循环中，会出现这样的情况：7%7 == 0，因此 7 在您的程序中看起来是错误的。这将发生在所有小于“while x < limit”循环限制的素数上，因为 x 将在某个时候成为您试图找到的素数。

于 2015-02-18T16:49:14.440 回答