python - 埃拉托色尼筛 - 寻找素数 Python

Question

澄清一下，这不是作业问题:)

我想为我正在构建的数学应用程序找到素数，并遇到了埃拉托色尼筛法。

我已经用 Python 编写了它的实现。但这非常慢。例如，如果我想找到所有小于 200 万的素数。它需要> 20分钟。（我在这一点上停止了它）。我怎样才能加快速度？

def primes_sieve(limit):
    limitn = limit+1
    primes = range(2, limitn)

    for i in primes:
        factors = range(i, limitn, i)
        for f in factors[1:]:
            if f in primes:
                primes.remove(f)
    return primes

print primes_sieve(2000)

更新： 我最终对这段代码进行了分析，发现从列表中删除一个元素花了很多时间。考虑到它必须遍历整个列表（最坏情况）才能找到元素，然后将其删除，然后重新调整列表（也许还有一些副本？），这是可以理解的。无论如何，我把字典列表扔掉了。我的新实现-

def primes_sieve1(limit):
    limitn = limit+1
    primes = dict()
    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
    return [i for i in primes if primes[i]==True]

print primes_sieve1(2000000)

score 120 · Accepted Answer

您没有完全实现正确的算法：

在您的第一个示例中，primes_sieve不维护要触发/取消设置的素数标志列表（如在算法中），而是不断调整整数列表的大小，这非常昂贵：从列表中删除项目需要移动所有后续项目下降一位。

在第二个例子中，primes_sieve1维护一个素数标志字典，这是朝着正确方向迈出的一步，但它以未定义的顺序迭代字典，并多余地剔除因子的因子（而不是像算法中那样只删除素数的因子）。您可以通过对键进行排序并跳过非素数来解决此问题（这已经使其速度提高了一个数量级），但直接使用列表仍然更有效。

正确的算法（使用列表而不是字典）看起来像：

def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

i*i（请注意，这还包括算法优化，即在素数的平方 ( ) 而不是其双倍开始非素数标记。）

score 15 · Accepted Answer

def eratosthenes(n):
    multiples = []
    for i in range(2, n+1):
        if i not in multiples:
            print (i)
            for j in range(i*i, n+1, i):
                multiples.append(j)

eratosthenes(100)

score 8 · Accepted Answer

从数组（列表）的开头删除需要将其后的所有项目向下移动。这意味着以这种方式从列表中从前面开始删除每个元素是一个 O(n^2) 操作。

您可以使用集合更有效地做到这一点：

def primes_sieve(limit):
    limitn = limit+1
    not_prime = set()
    primes = []

    for i in range(2, limitn):
        if i in not_prime:
            continue

        for f in range(i*2, limitn, i):
            not_prime.add(f)

        primes.append(i)

    return primes

print primes_sieve(1000000)

...或者，避免重新排列列表：

def primes_sieve(limit):
    limitn = limit+1
    not_prime = [False] * limitn
    primes = []

    for i in range(2, limitn):
        if not_prime[i]:
            continue
        for f in xrange(i*2, limitn, i):
            not_prime[f] = True

        primes.append(i)

    return primes

score 5 · Accepted Answer

快多了：

import time
def get_primes(n):
  m = n+1
  #numbers = [True for i in range(m)]
  numbers = [True] * m #EDIT: faster
  for i in range(2, int(n**0.5 + 1)):
    if numbers[i]:
      for j in range(i*i, m, i):
        numbers[j] = False
  primes = []
  for i in range(2, m):
    if numbers[i]:
      primes.append(i)
  return primes

start = time.time()
primes = get_primes(10000)
print(time.time() - start)
print(get_primes(100))

score 2 · Accepted Answer

我意识到这并不能真正回答如何快速生成素数的问题，但也许有些人会发现这种替代方法很有趣：因为 python 通过生成器提供惰性求值，所以可以完全按照所述实现 Eratosthenes 的筛子：

def intsfrom(n):
    while True:
        yield n
        n += 1

def sieve(ilist):
    p = next(ilist)
    yield p
    for q in sieve(n for n in ilist if n%p != 0):
        yield q


try:
    for p in sieve(intsfrom(2)):
        print p,

    print ''
except RuntimeError as e:
    print e

try 块在那里，因为算法一直运行直到它破坏堆栈，并且没有 try 块，显示回溯，将您想要看到的实际输出推到屏幕外。

score 2 · Accepted Answer

通过结合许多爱好者的贡献（包括上述评论中的 Glenn Maynard 和 MrHIDEn），我在 python 2 中提出了以下代码：

def simpleSieve(sieveSize):
    #creating Sieve.
    sieve = [True] * (sieveSize+1)
    # 0 and 1 are not considered prime.
    sieve[0] = False
    sieve[1] = False
    for i in xrange(2,int(math.sqrt(sieveSize))+1):
        if sieve[i] == False:
            continue
        for pointer in xrange(i**2, sieveSize+1, i):
            sieve[pointer] = False
    # Sieve is left with prime numbers == True
    primes = []
    for i in xrange(sieveSize+1):
        if sieve[i] == True:
            primes.append(i)
    return primes

sieveSize = input()
primes = simpleSieve(sieveSize)

在我的机器上以 10 的幂计算不同输入所需的时间是：

3：0.3 毫秒
4：2.4 毫秒
5 : 23 毫秒
6：0.26 秒
7 : 3.1 秒
8 : 33 秒

score 2 · Accepted Answer

使用一点numpy，我可以在 2 秒多一点的时间内找到所有低于 1 亿的素数。

有两个关键特性需要注意

切出的倍数i只为i最多的根n
设置使用的倍数i比显式的 python for 循环快得多。Falsex[2*i::i] = False

这两个显着加快了您的代码。对于低于 100 万的限制，没有可察觉的运行时间。

import numpy as np

def primes(n):
    x = np.ones((n+1,), dtype=np.bool)
    x[0] = False
    x[1] = False
    for i in range(2, int(n**0.5)+1):
        if x[i]:
            x[2*i::i] = False

    primes = np.where(x == True)[0]
    return primes

print(len(primes(100_000_000)))

score 1 · Accepted Answer

一个简单的速度技巧：定义变量“primes”时，将步长设置为 2 以自动跳过所有偶数，并将起点设置为 1。

然后你可以进一步优化，而不是 for i in primes，使用 for i in primes[:round(len(primes) ** 0.5)]。这将显着提高性能。此外，您可以消除以 5 结尾的数字以进一步提高速度。

score 1 · Accepted Answer

我的实现：

import math
n = 100
marked = {}
for i in range(2, int(math.sqrt(n))):
    if not marked.get(i):
        for x in range(i * i, n, i):
            marked[x] = True

for i in range(2, n):
    if not marked.get(i):
        print i

score 1 · Accepted Answer

这是一个更节省内存的版本（并且：适当的筛子，而不是试除法）。基本上，不是保留所有数字的数组，并删除那些不是素数的数字，而是保留一组计数器 - 每个发现的素数都有一个 - 并在假定的素数之前跳过它们。这样，它使用与质数成正比的存储空间，而不是最高质数。

import itertools

def primes():

    class counter:
        def __init__ (this,  n): this.n, this.current,  this.isVirgin = n, n*n,  True
            # isVirgin means it's never been incremented
        def advancePast (this,  n): # return true if the counter advanced
            if this.current > n:
                if this.isVirgin: raise StopIteration # if this is virgin, then so will be all the subsequent counters.  Don't need to iterate further.
                return False
            this.current += this.n # pre: this.current == n; post: this.current > n.
            this.isVirgin = False # when it's gone, it's gone
            return True

    yield 1
    multiples = []
    for n in itertools.count(2):
        isPrime = True
        for p in (m.advancePast(n) for m in multiples):
            if p: isPrime = False
        if isPrime:
            yield n
            multiples.append (counter (n))

您会注意到这primes()是一个生成器，因此您可以将结果保存在列表中，也可以直接使用它们。这是第一个n素数：

import itertools

for k in itertools.islice (primes(),  n):
    print (k)

而且，为了完整起见，这里有一个计时器来衡量性能：

import time

def timer ():
    t,  k = time.process_time(),  10
    for p in primes():
        if p>k:
            print (time.process_time()-t,  " to ",  p,  "\n")
            k *= 10
            if k>100000: return

以防万一您想知道，我还编写primes()了一个简单的迭代器（使用__iter__and __next__），它以几乎相同的速度运行。也让我惊喜！

score 1 · Accepted Answer

由于速度，我更喜欢 NumPy。

import numpy as np

# Find all prime numbers using Sieve of Eratosthenes
def get_primes1(n):
    m = int(np.sqrt(n))
    is_prime = np.ones(n, dtype=bool)
    is_prime[:2] = False  # 0 and 1 are not primes

    for i in range(2, m):
        if is_prime[i] == False:
            continue
        is_prime[i*i::i] = False

    return np.nonzero(is_prime)[0]

# Find all prime numbers using brute-force.
def isprime(n):
    ''' Check if integer n is a prime '''
    n = abs(int(n))  # n is a positive integer
    if n < 2:  # 0 and 1 are not primes
        return False
    if n == 2:  # 2 is the only even prime number
        return True
    if not n & 1:  # all other even numbers are not primes
        return False
    # Range starts with 3 and only needs to go up the square root
    # of n for all odd numbers
    for x in range(3, int(n**0.5)+1, 2):
        if n % x == 0:
            return False
    return True

# To apply a function to a numpy array, one have to vectorize the function
def get_primes2(n):
    vectorized_isprime = np.vectorize(isprime)
    a = np.arange(n)
    return a[vectorized_isprime(a)]

检查输出：

n = 100
print(get_primes1(n))
print(get_primes2(n))    
    [ 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]
    [ 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]

在 Jupyter Notebook 上比较 Eratosthenes 的 Sieve 和 brute-force 的速度。Eratosthenes 的筛分法比百万元素的蛮力法快 539 倍。

%timeit get_primes1(1000000)
%timeit get_primes2(1000000)
4.79 ms ± 90.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
2.58 s ± 31.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

score 1 · Accepted Answer

我认为必须可以简单地使用空列表作为循环的终止条件并想出了这个：

limit = 100
ints = list(range(2, limit))   # Will end up empty

while len(ints) > 0:
    prime = ints[0]
    print prime
    ints.remove(prime)
    i = 2
    multiple = prime * i
    while multiple <= limit:
        if multiple in ints:
            ints.remove(multiple)
        i += 1
        multiple = prime * i

score 1 · Accepted Answer

import math
def sieve(n):
    primes = [True]*n
    primes[0] = False
    primes[1] = False
    for i in range(2,int(math.sqrt(n))+1):
            j = i*i
            while j < n:
                    primes[j] = False
                    j = j+i
    return [x for x in range(n) if primes[x] == True]

score 1 · Accepted Answer

我能想到的最快的实现：

isprime = [True]*N
isprime[0] = isprime[1] = False
for i in range(4, N, 2):
    isprime[i] = False
for i in range(3, N, 2):
    if isprime[i]:
        for j in range(i*i, N, 2*i):
            isprime[j] = False

score 1 · Accepted Answer

我认为这是用eratosthenes方法查找素数的最短代码

def prime(r):
    n = range(2,r)
    while len(n)>0:
        yield n[0]
        n = [x for x in n if x not in range(n[0],r,n[0])]


print(list(prime(r)))

score 1 · Accepted Answer

我刚想出这个。它可能不是最快的，但除了直接添加和比较之外，我没有使用任何其他方法。当然，在这里阻止你的是递归限制。

def nondivsby2():
    j = 1
    while True:
        j += 2
        yield j

def nondivsbyk(k, nondivs):
    j = 0
    for i in nondivs:
        while j < i:
            j += k
        if j > i:
            yield i

def primes():
    nd = nondivsby2()
    while True:
        p = next(nd)
        nd = nondivsbyk(p, nd)
        yield p

def main():
    for p in primes():
        print(p)

score 1 · Accepted Answer

我制作了埃拉托色尼筛的单衬版本

sieve = lambda j: [print(x) for x in filter(lambda n: 0 not in map(lambda i: n % i, range(2, n)) and (n!=1)&(n!=0), range(j + 1))]

就性能而言，我很确定这无论如何都不是最快的，就可读性/遵循 PEP8 而言，这非常糟糕，但它的长度比任何东西都新颖。

编辑：请注意，这只是打印筛子并且不会返回（如果您尝试打印它，您将获得一个无列表，如果您想返回，请将列表理解中的 print(x) 更改为“x”。

score 0 · Accepted Answer

不确定我的代码是否有效，有人愿意发表评论吗？

from math import isqrt

def isPrime(n):
    if n >= 2: # cheating the 2, is 2 even prime?
        for i in range(3, int(n / 2 + 1),2): # dont waste time with even numbers
            if n % i == 0:
                return False
    return True

def primesTo(n): 
    x = [2] if n >= 2 else [] # cheat the only even prime
    if n >= 2:
        for i in range(3, n + 1,2): # dont waste time with even numbers
            if isPrime(i):
                x.append(i)  
    return x

def primes2(n): # trying to do this using set methods and the "Sieve of Eratosthenes"
    base = {2} # again cheating the 2
    base.update(set(range(3, n + 1, 2))) # build the base of odd numbers
    for i in range(3, isqrt(n) + 1, 2): # apply the sieve
        base.difference_update(set(range(2 * i, n + 1 , i)))
    return list(base)

print(primesTo(10000)) # 2 different methods for comparison
print(primes2(10000))

score 0 · Accepted Answer

获得主要数字的最快方法可能如下：

import sympy
list(sympy.primerange(lower, upper+1))

如果您不需要存储它们，只需使用上面的代码而不转换为list. sympy.primerange是一个生成器，所以它不消耗内存。

score 0 · Accepted Answer

使用递归和海象运算符：

def prime_factors(n):
    for i in range(2, int(n ** 0.5) + 1):
        if (q_r := divmod(n, i))[1] == 0:
            return [i] + factor_list(q_r[0])
    return [n]

score 0 · Accepted Answer

基本筛

速度numpy惊人。可能是最快的实现

# record: sieve 1_000_000_000 in 6.9s (core i7 - 2.6Ghz)
def sieve_22max_naive(bound):
    sieve = np.ones(bound, dtype=bool)  # default all prime
    sieve[:2] = False  # 0, 1 is not prime

    sqrt_bound = math.ceil(math.sqrt(bound))

    for i in range(2, sqrt_bound):
        if sieve[i]:
            inc = i if i == 2 else 2 * i
            sieve[i * i:bound:inc] = False

    return np.arange(bound)[sieve]


if __name__ == '__main__':
    start = time.time()
    prime_list = sieve_22max_naive(1_000_000_000)
    print(f'Count: {len(prime_list):,}\n'
          f'Greatest: {prime_list[-1]:,}\n'
          f'Elapsed: %.3f' % (time.time() - start))

段筛（使用更少的内存）

# find prime in range [from..N), base on primes in range [2..from)
def sieve_era_part(primes, nfrom, n):
    sieve_part = np.ones(n - nfrom, dtype=bool)  # default all prime

    limit = math.ceil(math.sqrt(n))
    # [2,3,5,7,11...p] can find primes < (p+2)^2
    if primes[-1] < limit - 2:
        print(f'Not enough base primes to find up to {n:,}')
        return

    for p in primes:
        if p >= limit: break

        mul = p * p
        inc = p * (2 if p > 2 else 1)
        if mul < nfrom:
            mul = math.ceil(nfrom / p) * p
            (mul := mul + p) if p > 2 and (mul & 1) == 0 else ...  # odd, not even

        sieve_part[mul - nfrom::inc] = False

    return np.arange(nfrom, n)[sieve_part]
    # return np.where(sieve_part)[0] + nfrom
    # return [i + nfrom for i, is_p in enumerate(sieve_part) if is_p]
    # return [i for i in range(max(nfrom, 2), n) if sieve_part[i - nfrom]]


# find nth prime number, use less memory,
# extend bound to SEG_SIZE each loop
# record: 50_847_534 nth prime in 6.78s, core i7 - 9850H 2.6GHhz
def nth_prime(n):
    # find prime up to bound
    bound = 500_000
    primes = sieve_22max_naive(bound)

    SEG_SIZE = int(50e6)

    while len(primes) < n:
        # sieve for next segment
        new_primes = sieve_era_part(primes, bound, bound + SEG_SIZE)
        # extend primes
        bound += SEG_SIZE
        primes = np.append(primes, new_primes)

    return primes[n - 1]


if __name__ == '__main__':
    start = time.time()
    prime = nth_prime(50_847_534)
    print(f'{prime:,} Time %.6f' % (time.time() - start))

python - 埃拉托色尼筛 - 寻找素数 Python

21 回答 21

基本筛

段筛（使用更少的内存）

Related

Reference