Optymalizuj sito Eratostenesa Dalej

Question

Napisałem Sito Eratostenesa - myślę - ale wygląda na to, że nie jest tak zoptymalizowane, jak mogłoby być. Działa, i dostaje wszystkie liczby pierwsze do N, ale nie tak szybko, jak miałem nadzieję. Wciąż się uczę Python - pochodzące z dwóch lat Jawa - więc jeśli coś nie jest szczególnie pythonowy potem przepraszać:

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 

Szukałem w innych pytań podobnych do tego ale nie mogę” t wymyślić, w jaki sposób niektóre bardziej skomplikowane optymalizacje będą pasowały do ​​mojego kodu. Jakieś sugestie?

EDYCJA: zgodnie z życzeniem, niektóre z innych optymalizacji, jakie widziałem, zatrzymują iterację pierwszej pętli przed limitem i pomijam różne numery - co według mnie jest optymalizacją koła?

EDIT 2: Oto kod, który wykorzystuje metodę, za PADRAIC:

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

Answer 1

nieco odmienne podejście: użyj bitarray reprezentować numery nieparzyste 3,5,7,... oszczędzając trochę miejsca w porównaniu z listą logicznych.

może to zaoszczędzić trochę miejsca, a nie tylko pomóc przyspieszenie ...

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) 

sam pomysł ponownie; ale tym razem pozwól bitarray obsługiwać wewnętrzną pętlę przy użyciu przypisania plastra. to może być szybciej.

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 

(nikt tego kodu zostało poważnie sprawdzone! Korzystania z opieki)

---

w przypadku szukasz generator liczb pierwszych w oparciu o inną metodę (wheel factorizaition) spojrzeć na this excellent answer .