[Project Euler] Primfaktorzerlegung?

[C4S3]

Hallo!

Bin über Project Euler gestolpert und finde die Idee gut, da man als Programmieranfänger/Laie ohnehin oft nicht weiß, was man programmieren soll. Da bietet sich sowas geradezu an.

Womit ich allerdings meine Probleme habe: Project Euler hat einen Fokus auf Mathematik - meine allergrößte Schwäche.
Schon jetzt beim 3. Beispiel verstehe ich teile der Aufgabenstellung nicht. (Nein, es ist keine Hausaufgabe, dafür bin ich schon ein wenig zu alt ).
Nach Recherche im Internet bin ich natürlich über kurz oder lang auf Wikipedia gelandet, nur der Artikel bringt mich nicht weiter, weil ich selbst da meine Probleme habe, den Inhalt wirklich zu verstehen. Mein letzter Schulbesuch ist schon fast zwei Dekaden her und als Handwerker war Primfaktorzerlegung nicht unbedingt ein Muss.

Ist es möglich, die Primfaktorzerlegung, einem Mathematik-Laien wie mir zu erkären?
Ich meine, mir ist schon klar was eine Primzahl ist, aber wie bitte muss das "Rezept" aussehen, damit man z.B. auf 6939 = 2^3 . 3 . 17^2 kommt?
Irgendwo muss man ja anfangen...

Geht man alle Positionen von 1 bis 6939 alle Zahlen durch, versucht dann 6939 durch eben jene Position zu teilen und wenn Modulo = 0 ist, guckt man noch, ob's ne Primzahl ist?

Kann jemand ein paar Minuten für eine Erklärung opfern?
Vielen Dank!

[numerix]

Wie man es konkret umsetzt, hängt von den Rahmenbedingungen ab:
Wie groß ist die Zahl, die zerlegt werden soll?
Ist es nur eine Zahl (oder eine Handvoll) oder eine größere Menge an Zahlen, deren Primfaktorzerlegung benötigt wird.

Ich schildere der Einfachheit halber ein mögliches Vorgehen, wenn eine (oder einige wenige) Primfaktorzerlegungen für nicht zu große Zahlen gesucht werden (sagen wir mal für n < 10^9 - dann wäre noch Luft nach oben hin).

Zunächst ermittelst du alle Primzahlen, die als Primfaktoren in Frage kommen (welche "in Frage kommen", verrate ich jetzt mal noch nicht; kannst ja mal drüber nachdenken). Das geht am schnellsten mit einem Siebverfahren (Stichwort: Eratosthenes).
Danach gehst du die Liste der Primfaktoren durch und ermittelst durch Probedivisionen, ob ein Primfaktor in n enthalten ist und ggf. wie oft (d.h. so lange durch denselben Primfaktor dividieren, bis ein Rest bleibt). Für das Ergebnis - also z.B. Primfaktor p ist k-mal enthalten - bietet sich ein dictionary an. Danach dann p^k von n abdividieren -> ergibt neues n.
Solange n nicht 1 ist oder in der Liste der Primfaktoren enthalten ist, weitermachen mit der Probedivision. Das war's eigentlich schon.

Viel Erfolg!

[BlackJack]

@C4S3: Man geht die Primzahlen durch, die kleiner oder gleich der zu zerlegenden Zahl sind, und versucht immer wieder durch die zu teilen, bis man bei 1 angelangt ist, und zählt dabei wie oft man durch welche Primzahl geteilt hat. Das Beispiel:

6939 teilbar durch 2? Ja = 3468, Ergebnis: [2]

3468 teilbar durch 2? Ja = 1734, Ergebnis: [2, 2]

1734 teilbar durch 2? Ja = 867, Ergebnis: [2, 2, 2]

867 teilbar durch 2? Nein, also nächste Primzahl.

867 teilbar durch 3? Ja = 289, Ergebnis: [2, 2, 2, 3]

289 teilbar durch 3? Nein.

289 teilbar durch 5? Nein.

289 teilbar durch 7? Nein.

289 teilbar durch 11? Nein.

289 teilbar durch 13? Nein.

289 teilbar durch 17? Ja = 17, Ergebnis: [2, 2, 2, 3, 17]

17 teilbar durch 17? Ja = 1, Ergebnis: [2, 2, 2, 3, 17, 17]

Und damit hat man das Ergebnis. Kann man jetzt noch kürzer schreiben, indem man die Anzahlen der jeweiligen Werte zählt: 2**3 * 3 * 17**2.

[C4S3]

Ich danke euch für die Erklärungen.
Ich habe auch dabei wieder zu kauen, werde mir aber dieses WE die Zeit nehmen und etwas über Eratosthenes (und dessen Sieb) lernen und auf Papier versuchen, ein paar Beispiele zu lösen.

Wird wohl ein wenig dauern, aber wenn ich denke, es verstanden zu haben, werde ich hier noch mal eine Nachricht in dem Thread hinterlassen.

Danke einstweilen.

[HWK]

Hier ein alter Thread zu diesem Thema.
MfG
HWK

[bremer]

Ich habe versucht, Eratosthenes umzusetzen, dabei erstellte ich diesen Code.

Code: Alles auswählen

n = 600851475143
table = [i for i in range(2, n+1, 2)]
print("Created table.")
i = 3
while i**2 <= n:
    for j in range(i, n+1, i):
        try:
            table.remove(j)
        except ValueError:
            pass
    i += 1
print(table)

Dabei geschieht das:

Traceback (most recent call last):
File "C:\Python31\projecteuler3.py", line 17, in <module>
table = [i for i in range(2, n+1, 2)]
File "C:\Python31\projecteuler3.py", line 17, in <listcomp>
table = [i for i in range(2, n+1, 2)]
MemoryError

[veers]

Das wundert dich bei N=600851475143? Eine 32bit Kiste kann das nicht mal Adressieren. Ausserdem sieht das Code auch falsch aus, zum einen ist list.remove langsam. Zum anderen verschiebst du so ja den Index jeweils.

Ich nehme mal an du möchtest folgende Aufgabe lösen:
http://projecteuler.net/index.php?section=problems&id=3

Dabei geht es ja um eine einzelne Zahl. Das Sieb ist jedoch "nur" dafür nützlich alle Primzahlen von 0 bis N zu finden.

Die Aufgabe lässt sich einfach mit Bruteforce lösen:

Code: Alles auswählen

für jede zahl i von 2 bis sqrt(N)+1:
  solange sich N durch i teilen lässt:
    N = N / i
  wenn n gleich 1 ist, ist i der grösste primfaktor. 

Theoretisch könntest du mit dem Sieb alle Primzahlen von bis sqrt(N) berechnen und nur diese Prüfen. Das ist in dem Fall jedoch nicht nötig.

Gruss,
Jonas

[Darii]

Ich habe versucht, Eratosthenes umzusetzen, dabei erstellte ich diesen Code.

Der Fehler steht doch da. Mal grob überschlagen, bräuchte deine Liste mindestens einen Speicherplatz von 4 TB.

[numerix]

Und du müsstest dir überlegen, was nun eigentlich willst:
Geht es "nur" um die Lösung "Euler Nr. 3": Dann nimm den Pseudocode von veers.

Willst du einen (allgemeineren) Algorithmus zur Primfaktorzerlegung implementieren, dann hängt das geeignete Verfahren von der Größe der Zahl ab. Bei der von dir genannten Größenordnung kommst du mit dem Verfahren aus, was ich weiter oben schon erläutert habe.
Wenn die Zahlen größer werden, genügt das nicht mehr.

Das Sieb des Eratosthenes sollte man aber auf jeden Fall mal implementiert haben.

[jbs]

Interessant finde ich diesen Ansatz: http://code.activestate.com/recipes/117119/

Vielleicht wurde das auch schon gepostet, dann bitte ich um Verzeihung.

[numerix]

Interessant finde ich diesen Ansatz: http://code.activestate.com/recipes/117119/

Das ist nett; allerdings nicht performant ...