进一步优化Eratosthenes筛 [英] Optimize Sieve of Eratosthenes Further

问题描述

我写了一个Eratosthenes筛子-我认为-但似乎它没有达到最佳状态.它可以工作，并且可以将所有素数提高到N，但速度却不如我希望的那样快.我仍然在学习Python(来自Java的两年时间)，因此，如果某些东西不是特别Pythonic的，我深表歉意:

I have written a Sieve of Eratosthenes--I think--but it seems like it's not as optimized as it could be. It works, and it gets all the primes up to N, but not as quickly as I'd hoped. I'm still learning Python--coming from two years of Java--so if something isn't particularly Pythonic then I apologize:

def sieve(self):
        is_prime = [False, False, True, True] + [False, True] * ((self.lim - 4) // 2)
        for i in range(3, self.lim, 2):
            if i**2 > self.lim: break
            if is_prime[i]:
                for j in range(i * i, self.lim, i * 2):
                    is_prime[j] = False
        return is_prime

我已经看过其他与此问题类似的问题，但是我无法弄清楚一些更复杂的优化如何适合我的代码.有什么建议吗?

I've looked at other questions similar to this one but I can't figure out how some of the more complicated optimizations would fit in to my code. Any suggestions?

根据要求，我看到的其他一些优化是在限制之前停止第一个for循环的迭代，并跳过不同的数字-我认为这是车轮优化?

as requested, some of the other optimizations I've seen are stopping the iteration of the first for loop before the limit, and skipping by different numbers--which I think is wheel optimization?

这是用于Padraic的方法的代码:

EDIT 2: Here's the code that would utilize the method, for Padraic:

primes = sieve.sieve()
for i in range(0, len(primes)):
    if primes[i]:
        print("{:d} ".format(i), end = '')
print() # print a newline

推荐答案

一种略有不同的方法:使用位数组表示奇数3,5,7,...与布尔值列表相比节省了一些空间.

a slightly different approach: use a bitarray to represent the odd numbers 3,5,7,... saving some space compared to a list of booleans.

这可能仅节省一些空间而无助于加速...

this may save some space only and not help speedup...

from bitarray import bitarray

def index_to_number(i): return 2*i+3
def number_to_index(n): return (n-3)//2

LIMIT_NUMBER = 50
LIMIT_INDEX = number_to_index(LIMIT_NUMBER)+1

odd_primes = bitarray(LIMIT_INDEX)
# index  0 1 2 3
# number 3 5 7 9

odd_primes.setall(True)

for i in range(LIMIT_INDEX):
    if odd_primes[i] is False:
        continue
    n = index_to_number(i)
    for m in range(n**2, LIMIT_NUMBER, 2*n):
        odd_primes[number_to_index(m)] = False

primes = [index_to_number(i) for i in range(LIMIT_INDEX)
          if odd_primes[i] is True]
primes.insert(0,2)

print('primes: ', primes)

同样的想法；但这一次让bitarray使用切片分配处理内部循环.这可能会更快.

the same idea again; but this time let bitarray handle the inner loop using slice assignment. this may be faster.

for i in range(LIMIT_INDEX):
    if odd_primes[i] is False:
        continue
    odd_primes[2*i**2 + 6*i + 3:LIMIT_INDEX:2*i+3] = False

(此代码均未经过认真检查！请小心使用)

(none of this code has been seriously checked! use with care)

如果您正在寻找基于其他方法的素数生成器(车轮分解 )，请查看此优秀答案.

in case you are looking for a primes generator based on a different method (wheel factorizaition) have a look at this excellent answer.

这篇关于进一步优化Eratosthenes筛的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！