Eratosthenes Elek Optimize Etmek

Question

Bir Elek Eratosthenes yazdım - Sanırım - ama olabildiğince optimize edilmiş gibi değil. Çalışır ve N'ye kadar tüm primleri alır, ama umduğum kadar çabuk değil. Hala Python öğreniyorum - Java iki yıl gelen - bir şey özellikle Pythonic değilse o halde ben özür dilerim:

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 

Ben buna benzer diğer sorular baktım ama yapamam Bazı daha karmaşık optimizasyonların benim koduma nasıl uyduğunu anlamaya çalışıyorum. Baska öneri?

DÜZENLEME: İstediğim gibi, gördüğüm diğer optimizasyonlardan bazıları, sınırlamadan önce ilk döngü döngüsünün yinelemesini durdurarak, farklı sayılarla atlama yapmaktır - ki bu, tekerlek optimizasyonu mu?

DÜZENLEME 2: İşte Pádraic için, yöntem kullanmak istiyorum kod:

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

Answer 1

biraz farklı bir yaklaşım: boole listeye göre biraz boşluk tasarrufu tek sayılar 3,5,7,... temsil etmek üzere bir bitarray kullanın. Bu değil sadece bir hıza yardımcı olan bazı yer kazanmak olabilir

...

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) 

Aynı düşünce tekrar; ama bu sefer bitarray dilimleme atamasını kullanarak iç döngüyü idare etsin. Bu daha hızlı olabilir. Eğer farklı bir yöntemle (wheel factorizaition) dayalı bir asal jeneratör aradığınız durumunda

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 

(Bu kodun hiçbiri ciddi kontrol edilmiştir! özenle kullanmak)

---

this excellent answer de bakabilirsiniz .