große listen erstellen

[pythonizer]

Hallo,
ich muss für eine Aufgabe große Zahlen testen ob sie Primzahlen sind. Eigentlich bin ich C++ Programmierer, die Zahlen um die es mir geht, können nicht ohne weiteres dort verarbeitet werden. Deswegen habe für die Aufgabe Python genommen. Programmiere damit also erst einen Tag damit.

Für den Test wird zunächst eine Liste von Primzahlen erstellt.

Code: Alles auswählen

def genPrims(max):
  global maxNum
  global primNums

  if max <= 2:
    raise Exception, 'max sollte größer 2 sein'

  maxNum = max
  primNums = primNums + [2]

  for i in range(3, max):
    for j in primNums:
      if (i % j) == 0:
        break
      else:
        pass
    else:
      primNums = primNums + [i]

Das Problem dabei ist dass ich ein MemoryError bekomme für range(3, 100000000)
Wobei der maximale Wert für die Aufgabe etwa 100-1000 mal höher angesetzt ist.

Weiß jemand wie das Problem mit dem Speicher-Fehler gelöst werden kann.

[schlangenbeschwörer]

Hi!
Em...ich kenn C++ ja nicht, aber es gibt Sachen, die mit C++ nicht gehen, aber mit Python gehen sollen?
Und für so große Zahlen ist range auch nicht ausgelegt. Python ist toll, und vlt. geht das auch über umwege, aber für diese Aufgabe gibt es bestimmt andere Sprachen, die da geeigneter sind.
Außerdem ist der Code auch nicht der schnellste. Mit der Suche findest du hier ein paar Primzahlscripte, die vmtl. um einiges schneller sind.
Gruß, jj

[pythonizer]

Hi!
Em...ich kenn C++ ja nicht, aber es gibt Sachen, die mit C++ nicht gehen, aber mit Python gehen sollen?

In C++ kann man das auch lösen, mit zusätzlichen Libraries (oder selbstgemachte). In C++ kann der int typ den nur maximalen Wert von 2^32-1 annehmen. Ist mir zu wenig.
Python wollte ich schon immer mal lernen, habe jetzt also einen Vorwand gefunden.

Und für so große Zahlen ist range auch nicht ausgelegt. Python ist toll, und vlt. geht das auch über umwege,

Wo du es sagst, ist mir while-Schleife eingefallen. Muss mal ausprobieren.

Edit:
Ich würde sagen, der code so wie ich ihn verwende ist der schnellste.
Der Grund ist, dass ich die Liste nur ein mal generieren muss. Später kann ich ja einfach den Wert in der Liste suchen. Ist er da => Primzahl. Nicht da => keine.
Linearer Aufwand. Was will man mehr?
Außer die Zahl ist größer als Maximaler wert. Aber die Zahlen sind für die Aufgabe vorgegeben. Also ist kein Problem

[EyDu]

An Stelle von "range" kannst du "xrange" verwenden (sieh Doku). Über Primzahlen sollte sich hier im Forum sonst noch genug finden lassen.

Und dann noch ein paa Kleinigkeiten:
1. Mach aus den "global"s Parameter
2. Die Exception ist so allgemein, dass du beim Abfragenalle anderen gleich mit verschluckst
3. Der Name "max" verdeckt eine Built-In-Funktion

Ich würde dir empfehlen eine Liste von Primzahlen zu organisieren (Googel liefert bestimmt einiges), denn diese Berechnung wird wirklich (wirklich!) lange dauern.

[EyDu]

Ich würde sagen, der code so wie ich ihn verwende ist der schnellste.

Sind wir da nicht ein wenig übermütig ? Du testes zum Beispiel eine Zahl gegen ALLE gefunden Primzahlen, das ist aber gar nicht nötig.

Und eine Liste ist auch nicht gerade die geschickteste Wahl. Bei deiner Angestrebten maximalen Zahl von 100000000000 wird du so in etwa 4 Milliarden Primzahlen erhalten. Du solltest vielleicht noch mal über die Struktur deines Programmes nachdenken.

[pythonizer]

ok, ihr habt recht. hab jetzt die for-range schleife in while umgeändert. läuft schon seit > 20 minuten. ende noch nicht in sicht.
Lohnt sicht vielleicht nicht für die Paar Zahlen, die nachher getestet werden.

Stimmt, alle Zahlen müssen nicht geprüft werden, reicht bis Wurzel(i).

Für die suche könnte man noch binäre suche verwenden, da die liste schon sortiert ist.

Eine Primzahlenliste runterladen? Wo bleibt da der Spaß?

Edit:
Beim Itererieren von i kann man auch i = i+2 schreiben. Alle geraden Zahlen sind eh nicht prim. Dadurch muss ich nur die Hälfte der Zahlen testen.

Jetzt nur noch Iterative Folge für int-Wurzel finden...

[EyDu]

Edit:
Beim Itererieren von i kann man auch i = i+2 schreiben. Alle geraden Zahlen sind eh nicht prim. Dadurch muss ich nur die Hälfte der Zahlen testen.

Jetzt nur noch Iterative Folge für int-Wurzel finden...

Natürlich kann man sich auch alles noch mal selber ausdenken, aber wenn ich mich richtig erinnere, habe ich die Foren-Suche schon laaange erwähnt.

[pythonizer]

Natürlich kann man sich auch alles noch mal selber ausdenken, aber wenn ich mich richtig erinnere, habe ich die Foren-Suche schon laaange erwähnt.

Ich weiß. Aber ich studiere mathe. finds auch interessant es selbst rauszufinden.

Auch wenns Offtopic ist:
Wenn ich nichts falsch gemacht habe, dann sollte so theoretisch schneller laufen: Hab für Zahlen bis 100 getestet, sieht in Ordnung aus.

Code: Alles auswählen

def genPrims(toNum):
  global maxNum
  global primNums

  if toNum < 2:
    raise Exception, 'max < 2'

  maxNum = toNum
  primNums = primNums + [2]

  i = 3
  while i < toNum:
    for j in primNums:
      if j*j > i:
        primNums = primNums + [i]
        break
      if (i % j) == 0:
        break
    i = i+2 # Alle ungeraden testen reicht auch

Mir fällt nichts mehr ein. Jetzt schaue ich mir auch andere an

Edit:
wurzel berechnen ist unnötig. j*j > i tuts auch.

[BlackJack]

Der übliche Weg ist der Algorithmus des "Sieb des Eratostenes" (wenn ich den Namen nicht mal wieder falsch geschrieben habe).

Andererseits: Wofür brauchst Du die Primzahlen denn? Würde ein probalistischer Test wie der von Miller-Rabin eventuell auch ausreichen?

Wenn ich ein Sieb schreiben wollen würde, das den Speicher zu sprengen droht, würde ich erstmal versuchen eine möglichst speichersparende Datenstruktur zu wählen. Das wäre dann wohl ein Bit pro Zahl, weil man ja nur speichern müsste ob die Zahl prim ist oder nicht. Und für die geraden Zahlen muss man keine Bits verschwenden, also nochmal die Hälfte an Speicherplatz gespart.

Das wären für Zahlen bis 100000000000 aber immer noch über 6 Gigabyte. Falls Dir eine Null weniger ausreicht, dann sind die ca. 620 Megabyte etwas realistischer.

Das Programm würde ich dann aber auf jeden Fall so auslegen, dass man es kontrolliert unterbrechen und später weiterrechnen lassen kann. Und Du solltest viiiiieeel Zeit mitbringen.

[pythonizer]

wir müssen als aufgabe ein programm schreiben, dass a = b²+c² lösen kann. Wobei a,b,c natürliche Zahlen und a gegeben. Das Programm habe ich schon. Bin paar mal durchgegangen hats auch funktioniert. Da ich sonst nichts zu tun habe, wollte einen Test dazu schreiben. Dazu gibt eine Formel die angibt, wieviele Lösungen die Gleichung hat. Dafür werden Primfaktoren der Zahl a benötigt. Die Fehlerwahrscheinlichkeit bei den zufallsbasierten Tests ist zwar niedrig. Ich kann das aber so vom psychologischen Standpunkt nicht akzeptieren, dass sie nicht genau sind.

Über das Speicherproblem habe ich garnicht nachgedacht. Das Problem ist eh die generierung. Der letzte Code läuft bei mir schon seit einer Stunde für die Zahl 100000000 (ist relativ klein), Speicherverbrauch von python wird im Moment auf 23% von 256 Mb angezeigt. Ich breche lieber ab und gehe schlafen.