Prime Generator (für Spoj Lösung)

Question

Ich habe mehrere Tage mit diesem Prime Generator Algorithmus für SPOJ Problem zu kämpfen. Der Problemzustand zum Drucken von mindestens 100000 Primzahlen aus einer Zahl m, n mit n < = 1000000000 in 6 Sekunden. Ich habe diese Implementierung, die 100000 Prime in 11.701067686080933 Sekunden drucken. Ist es möglich, die Zeitbeschränkung (6s) in Python zu übertreffen? Ich fühle, dass ich etwas in meiner segmentierten Siebfunktion vermisse, weil ich es nur implementiert habe, wie ich den Algorithmus verstehe, vielleicht kann eine Änderung es besser machen.

Einige Hilfe würde hier geschätzt.

def sieveOfErosthen(m): 
    limit=m+1 
    prime=[True]*limit 

    for i in range(2,int(m**0.5)): 
     if prime[i]: 
      for x in range(i*i,limit,i): 
       prime[x]=False 
    return prime 

def segmentedSieve(m,n): 
    limit= n+1 
    segment=[True]*limit 

    for j in range(2,int(n**0.5)): 
     if sieveOfErosthen(j): 
      for b in range(j*(m//j),limit,j): 
       if b >j: 
        segment[b]=False 
    for v in range(m,limit): 
     if segment[v]: 
      print(v) 
    return True 

Answer 1

Dieser Code ist eine Katastrophe. Beginnen wir mit dem grellsten Fehler beginnen:

if sieveOfErosthen(j): 

(Dies ist besonders verwirrend ist als Original-Code diese Funktion nicht definiert haben, sondern definiert stattdessen EratosthenesSieve() - später Herausgeber Ihrer Post eine auf die andere abgebildet, die ich bin Annahme ist richtig.) Was gibt sieveOfErosthen(j) zurück? Er gibt ein Array zurück, also im booleschen Kontext von if ist dieser Test immer True, da das Array immer mindestens ein Element enthält, wenn j positiv ist!

Ändern Sie dies zu if True: und sehen Sie, dass Ihre Ausgabe nicht ändert. Was übrig bleibt, ist ein sehr ineffizienter Siebalgorithmus, die wir auf verschiedene Weise beschleunigen kann:

def segmentedSieve(m, n): 
    primes = [] 
    limit = n + 1 
    segment = [True] * limit 

    if limit > 0: 
     segment[0] = False 

     if limit > 1: 
      segment[1] = False 

    for j in range(2, int(limit**0.5) + 1): 
     if segment[j]: 
      for b in range(j * j, limit, j): 
       segment[b] = False 

    for v in range(m, limit): 
     if segment[v]: 
      primes.append(v) 

    return primes 

Dieser Code kann leicht die ersten 100.000 Primzahlen in einem Bruchteil einer Sekunde finden, aber letztlich, wenn n <= 1000000000 (eine Milliarde) dann müssen wir den schlimmsten Fall annehmen, dh die letzten 100.000 Primzahlen in 6 Sekunden für ein passendes m in segmentedSieve(m, 1000000000), welches diesen Code Minuten braucht, nicht Sekunden.

Schließlich haben Sie kein segmentiertes Sieb implementiert - Sie haben ein normales Sieb implementiert und den gewünschten Bereich einfach überflogen. Ich empfehle Ihnen, lesen Sie über segmented sieves in Wikipedia, oder anderswo, und beginnen Sie erneut, wenn Sie ein segmentiertes Sieb benötigen.

Answer 2

Um dieses Problem zu lösen, müssen Sie Segmentiertes Sieb verwenden. gibt es einige gute Ressourcen überprüfen Sie bitte diese geeksforgeeks quora

https://discuss.codechef.com/questions/54416/segmented-sieve https://github.com/calmhandtitan/algorepo/blob/master/numberTheory/sieve_fast.cpp