Mathematik/Informatik-Problem

[beatnut]

Nabend, stehe hier vor nem Problem:

- x = y^z (sprich x ist gleich y hoch z,)
- y ist eine Primzahl, z eine natürliche Zahl

Gegeben ist x. Wie finde ich möglichst elegant heraus, ob es ein Zahlenpaar y&z gibt, die zusammen x ergeben? Ne äußerst dreckige Methode hab ich schon, ist aber äußerst rechenintensiv.

Achja: Natürlich möchte ich die Werte von y (wie gesagt Primzahl) und z (natürlich Zahl) dann auch wissen.

Achja: Bei mehreren möglichen Lösungen (zB x=81 -> 9^2, 3^4) ist nur die Lösung mit dem niedrigsten Exponenten von Interesse. Edit: Ok, Scheiß, Beispiel: ) ist keine Primzahl...

[Kermit]

Ich würde erstmal die Gleichung umstellen:

y^z/x=1
zlog(y)/log(x)=1
zlog(y)=log(x)
z=log(x)/log(y)

x hast du ja gegeben oder definierst du dir in deinem Programm, keine Ahnung, was du da benutzt. Dann definierst du dir die y als Menge der Primzahlen.
Dann lässt du einfach ne Schleife durchlaufen, die abbricht, sobald das Ergebnis von log(x)/log(y) eine natürliche Zahl ist(du sucht ja auch nur die Lösung mit dem kleinsten Exponenten, also interessieren dich die anderen Lösungen ja nicht) und lässt dir y und z ausgeben.

[beatnut]

Jo, mach ich momentan auch so ähnlich. Mit dem Sieb des Eratosteles hol ich mir die Primzahlen bis SQRT(x). Und ab da probiere ich aus. Dachte es gibt da noch was schöneres...

[Steffen M.]

Jo, mach ich momentan auch so ähnlich. Mit dem Sieb des Eratosteles hol ich mir die Primzahlen bis SQRT(x). Und ab da probiere ich aus. Dachte es gibt da noch was schöneres...

Naja, es gibt halt noch andere Verfahren, um die Primzahlen selbst zu generieren. Z.B. eine Zahl beliebig wählen und dann (mehrfach) den Miller-Rabin-Test (das ist ein probabilistischer Algorithmus, der mit Zufallszahlen arbeitet und daher Fehler macht, daher mehrfach aufrufen) drauf loslassen.

Miller-Rabin ist insbesondere für sehr große Primzahlen, wie man sie für die Kryptographie braucht, von Vorteil. Man würfelt willkürlich eine Zahl und testet. Ist sie nicht prim, würfelt man eine neue.

Ich bezweifle aber, dass Dir Miller-Rabin hier viel bringt, wenn Du ja eh die Primzahlen "der Reihe nach" brauchst, um sie durchprobieren zu können. Denn die liefert Dir halt Eratosthenes quasi direkt, während Du bei Miller-Rabin ja immer würfeln und dann noch mehrfach testen müsstest.

Eine Möglichkeit wäre noch eine Verbesserung von Eratosthenes, das Atkin-Sieb.

Ansonsten fällt mir auch kein besserer Weg ein.

Gruß,
Steffen