Memoization mit Primzahlengenerator

Question

Ich habe eine Python-Klasse, die die n-te Primzahl erzeugt, indem sie bei der n-1ten Primzahl beginnt und inkrementiert. Dann wird durch alle Primzahlen bereits in der Liste bis zum Boden (sqrt (Kandidat)) geteilt. Aber meine Klasse gerät irgendwo in eine unendliche Schleife und ich kann nicht verstehen warum.

class prime_list(): 
    def __init__(self): 
     self.primelst = [1] 
     self.n = 1 

    def increment(self): 
     self.n+=1 
     candidate = self.primelst[-1]+1 
     limit = int(math.floor(math.sqrt(candidate))) 
     prime = True 
     while True: 
      for p in self.primelst: 
       if p>limit: 
        break 
       if (candidate % p) == 0: 
        prime = False 
        break 
      if prime: 
       self.primelst.append(candidate) 
       return 
      else: 
       candidate += 1 
       limit = int(math.floor(math.sqrt(candidate))) 
       prime = True 

if __name__=="__main__": 
    p = prime_list(): 
    p.increment() 

Answer 1

Das Problem ist, dass Sie 1 als Startwert in Ihrer Hauptliste setzen. Die increment-Funktion sucht dann nach Zahlen, die nicht durch 1 teilbar sind. Da es solche Nummern nicht gibt, sucht es für immer.

Sie sollten mit 2 als erste kleinste Primzahl beginnen oder einen Sonderfall hinzufügen, der die Generierung der ersten Primzahl behandelt.

Answer 2

Dies ist nicht genau eine Sprache oder Algorithmus Frage, sondern eine Debugging-Frage :). Fügen Sie vier Druckanweisungen innerhalb Ihrer Schleife hinzu (eine bei jeder bedingten Verzweigung) und Sie werden sehr schnell sehen, warum Ihr Programm nicht zu enden scheint. Es ist viel besser herauszufinden, was passiert durch Untersuchung selbst (jemanden lehren zu fischen, anstatt ihnen einen Fisch zu geben ...).

Viel Glück!

Answer 3

Werfen wir einen Lauf tun:

// self.primelst = [1] 
// self.n = 1 

def increment(self): 
     self.n+=1 // self.n = 2 
     candidate = self.primelst[-1]+1 //candidate = 2 
     limit = int(math.floor(math.sqrt(candidate))) // limit = 1 
     prime = True // prime = True 
     while True: 
      for p in self.primelst: // p = 1 
       if p>limit: // False 
        break // Does not go here 
       if (candidate % p) == 0: // 2 % 1 == 0: True 
        prime = False // prime = False 
        break // breaks 
      if prime: // False 
       self.primelst.append(candidate) // Does not go here 
       return // Does not return 
      else: // Goes here 
       candidate += 1 // candidate = 3 
       limit = int(math.floor(math.sqrt(candidate))) // limit = 1 
       prime = True // prime = True 

So ist die while-Schleife endlos wiederholt. Der Algorithmus ist falsch.

Answer 4

Einige Hinweise, zusätzlich zu dem Update von anderen beschrieben:

• Sie nicht self.n verwenden und wird es nicht brauchen, da Python Listen ihrer Länge kennen.
• Sie könnten jedoch einige Caching verwenden, um die Anzahl der Primzahlen zu überprüfen, um eine komplexe Berechnung zu vermeiden.
• primelst ist hässlich wie ein Bezeichner: solche Vokale auszulassen ist höchst unpythonisch, und das Einschließen eines Typnamens in den Bezeichnernamen ("Liste") widerspricht dem Geist der Entenschrift. Benennen Sie nur Container mit Plural.
• Bevorzugen Sie kurze Funktionen. Die Primzahlerkennung aus der Add-to-List-Logik herausrechnen und der Code wird stark vereinfacht. Es ist schwierig, sowohl Brüche als auch Rückgaben innerhalb einer verschachtelten Schleife zu haben.
• Sie könnten die Hauptfunktion "increment" zu einem Generator machen und während des Generierens Zugriff auf die benötigten Primes erhalten. :)
• Es gibt Werkzeuge in der Standardbibliothek, die Sie verwenden können, um (a) unbegrenzte, gezählte Schleifen zu machen und (b) jeden Teiler in einem Bereich zu prüfen.

So:

class prime_list(): 
    def __init__(self): 
     self.primes = [2] 
     self.to_use = 1 


    def test(self, candidate): 
     # Check if we need to expand the list of used primes. 
     # Written a bit paranoid-ly 
     while len(self.primes) > self.to_use: 
      next = self.primes[self.to_use] 
      # Note the mathematical rearrangement. :) 
      if candidate <= next * next: self.to_use += 1 
     # Test all the primes <= sqrt(candidate). 
     return all(candidate % p != 0 for p in self.primes[:self.to_use]) 


    def __iter__(self): 
     import itertools 
     for candidate in itertools.count(3): 
      if self.test(candidate): 
       self.primes.append(candidate) 
       yield candidate 


if __name__ == "__main__": 
    my_primes = prime_list() 
    for p in my_primes: 
     print "Generated:", p 
     if p > 1000000: break 
    print "Number of primes generated:", len(my_primes.primes) 

Answer 5

Karl Knechtel Antwort ist richtig, aber träge; Das Problem ist, dass to_use zu weit und zu früh fortgeschritten ist.

Hier ist meine geänderte Version - ich habe die Kommentare entfernt.

class prime_list(): 
    def __init__(self): 
     self.primes = [2] 
     self.to_use = 0 


def test(self, candidate): 
    next = self.primes[self.to_use] 
    if candidate >= next * next: 
     self.to_use += 1 
     print candidate, next 
    return all(candidate % p != 0 for p in self.primes[:self.to_use]) 


def __iter__(self): 
    import itertools 
    for candidate in itertools.count(3,2): 
     if self.test(candidate): 
      self.primes.append(candidate) 
      yield candidate 


if __name__ == "__main__": 
    my_primes = prime_list() 
# print my_primes.primes[0] 
    for p in my_primes: 
     print "Generated:", p 
     if p > 1000000: break 
     sum += p 
    print "Number of primes generated:", len(my_primes.primes)