Uhnz - Sa 25.10.08 13:35
Titel: Primaftorzerlegung und Primzahlen???

---

Hallo,

ich komme einfach nicht weiter ich erarbeite mir gerade ein Programm und komme gerade nicht weiter.
Ich möchte gerne eine Zahl in ihre Primfaktoren zerlegen und anschließend alle Primafaktoren ausgeben also zB 3*7*7 kann jemand mir da weiterhelfen???

Außerdem möchte ich gerne eine Zahl darauf testen ob sie eine Primzahl ist aber ohne sie vorher in ihre Primfaktoren zu zerlegen.
Anschließend möchte ich nur ein ja oder ein nein auf dem Bildschirm ausgeben lassen. Ich brauche bei dieser Lösung eine möglichst Effiziente, da auch große Zahlen im 5stelligen Bereich schnell getestet werden sollen.

Vielen Dank schon mal im Vorraus.

BenBE - Sa 25.10.08 13:50
Titel: Re: Primaftorzerlegung und Primzahlen???

---

Uhnz hat folgendes geschrieben :

Hallo, ich komme einfach nicht weiter ich erarbeite mir gerade ein Programm und komme gerade nicht weiter. Ich möchte gerne eine Zahl in ihre Primfaktoren zerlegen und anschließend alle Primafaktoren ausgeben also zB 3*7*7 kann jemand mir da weiterhelfen???

Hast Du die Forensuche schon bemüht? Grad die Algo & Opti-Sparte bietet hier reichlich Ansatzpunkte

Uhnz hat folgendes geschrieben :

Außerdem möchte ich gerne eine Zahl darauf testen ob sie eine Primzahl ist aber ohne sie vorher in ihre Primfaktoren zu zerlegen.

Pseudo-Primzahlen-Test nach Rabin\Miller. Primalität gegen 2,3,5,7 und 11 prüfen, sollte für Cardinal ausreichen. Wobei der normal sich erst ab 100-stelligen Zahlen wirklich lohnt ...

Uhnz hat folgendes geschrieben :

Anschließend möchte ich nur ein ja oder ein nein auf dem Bildschirm ausgeben lassen. Ich brauche bei dieser Lösung eine möglichst Effiziente, da auch große Zahlen im 5stelligen Bereich schnell getestet werden sollen.

Große Zahlen fangen bei mir ab 100 Stellen an ... Die Faktorisiert man dann aber ein wenig anders, als mit dem Euklidschen Sieb oder nem Primzahl-Rad ...

Uhnz hat folgendes geschrieben :

Vielen Dank schon mal im Vorraus.

MfG,
BenBE.

Hidden - Sa 25.10.08 14:01

---

Hi und :welcome: in der EE,

E: Mist, zu spät :(

Ich vermute mal es handelt sich um eine Aufgabe ohne tieferen Sinn. Ansonsten macht es je nach Anwendungszweck vielleicht auch Sinn, die Zahlen direkt in ihrer Primfaktorzerlegung im Speicher zu haben. Multiplikationen und Divisionen werden dadurch ziemlich einfach([2,3,3,5] = [2^1,3^2,5^1]; [2,3,3,5] / [2,4,4,5] = [3^2,4^-2]), also zu simplen Additionen/Subtraktionen.

Diese wiederum werden allerdings ein Stück schwerer, da sie, sollten sie doch einmal notwendig sein, nach möglichem Ausklammern erst wieder in das alte Vormat zurückgerechnet werden müssen.

mfG,

Thorsten83 - Sa 25.10.08 15:41

---

Hey,

letztendlich schließe ich mich meinen Vorrednern an,
wenn es "nur" um 5-stellige Zahlen geht kannst du das ungefähr beliebig programmieren :)