primfaktorzerlegung

Neue Frage »

prim Auf diesen Beitrag antworten »
primfaktorzerlegung
hi
ich suche ein kleine zahl n für die eine primfaktorzerlegung schwierig ist. um genau zu sein bei dem ein matheprogramm(mathlab,mathematica,maple...) länger benötigt als normal sie zu finden. eine etwas komische frage aber ich hoffe ihr könnt trotzdem helfen.
mfg prim
JochenX Auf diesen Beitrag antworten »

Zitat:
ich suche ein kleine zahl n

-7123571285712758912579012375237523795249572495

die ist sehr klein z.b.



definiere klein doch mal etwas genauer
prim Auf diesen Beitrag antworten »

also meine aufgabe genau lautet das ich eine kleine zahl (wie klein weiss ich selber nicht) finden soll, die mit einem matheprogramm nicht schneller als 10 sek findbar ist. gehen wir einfach von einem 2ghz pc aus. das problem ist das ich keine "kleine" zahl finde. erst ab zahlen die bei mir ca. 10stellig sind macht mein rechner schlapp aber vorher keine chance. aber ich hab auch nur willkürliche eingetippt. also die eigentliche frage ist ab wann eine primfaktorzerlegung für den rechner komplizierter wird....
gast1 Auf diesen Beitrag antworten »

Die Zahl ist schwerer zu faktorisieren, wenn sie Produkt zweier großer Primzahlen ist.
prim Auf diesen Beitrag antworten »

das ist mal ein ansatz. aber 10 sek sind doch ganz schön lange ist mir aufgefallen. klein ist hier wirklich relativ wie es aussieht.
JochenX Auf diesen Beitrag antworten »

klein ist insbesondere relativ, da du vermutlich: ganzzahlig und POSITIV zusätzlich voraussetzt, oder!?
 
 
prim Auf diesen Beitrag antworten »

das kommt wohl auch noch dazu. aber vielleicht ist mein pc auch einfach zu schnellAugenzwinkern 10 sek ist bei mir nur mit sehr grossen zahlen zahlen hinzukriegen. aber vielleicht gibts ja besondere zahlen die nicht so einfach zerlegbar sind?????
AD Auf diesen Beitrag antworten »

Versuch mal, die Zahl

code:
1:
4344269888365420646561189337982712540862320655091014941197732274401129329224227519682504576978654093


zu faktorisieren. Wenn du das heute noch schaffst, hast du einen echt guten Algorithmus, mit dem du noch sehr viel Geld verdienen kannst. Wink
JochenX Auf diesen Beitrag antworten »

pö, die ist doch prim
sieht man doch sofort! smile
AD Auf diesen Beitrag antworten »

Dann gehört Mathematica nicht zu "man":

code:
1:
PrimeQ[4344269888365420646561189337982712540862320655091014941197732274401129329224227519682504576978654093]

liefert False, und das im Bruchteil einer Sekunde. Wenn nur die Zerlegung auch so einfach wär...

EDIT: Sch... bei Copy+Paste wurde wieder mal die Hälfte unterschlagen - korrigiert.
JochenX Auf diesen Beitrag antworten »

okay, das heißt also mathematica findet schnell einen (oder mehrere) primteiler, aber die weiteren lassen sich nicht so schnell finden!?

dann lässt sich das ganze doch durch teilen durch diese leicht zu findenden primteiler im sinne der aufgabe optimieren, oder....?

mfg jochen


*primzahl-brille-putz*
ja jetzt sehe ich die nichtprimheit auch ^^
AD Auf diesen Beitrag antworten »

Zitat:
Original von LOED
okay, das heißt also mathematica findet schnell einen (oder mehrere) primteiler

Nein - wie kommst du darauf? Es erkennt nur, wann eine Zahl garantiert keine Primzahl ist. Dazu muss man keine Teiler finden! Stichwort: Kleiner Fermat.
JochenX Auf diesen Beitrag antworten »

was ich bei google findet, sagt mir eher nichts....

http://www.mathe-schule.de/download/pdf/...Satz_Fermat.pdf

verwirrt


edit: kein wuinder, das soll wohl nur eine anwendung sein
edit: das also isser

Zitat:
Für alle Primzahlen p und alle natürlichen Zahlen n, die kein Vielfaches von p sind, gilt:

n^(p-1) - 1 ist teilbar durch p
AD Auf diesen Beitrag antworten »

Na das ist er doch, du hast doch EZT gehört (war das nicht die Abkürzung). Also "PrimeQ" testet für einige kleine Zahlen a mit 1<a<p, ob



gilt. Stimmt das auch nur für eines dieser a nicht, dann kann p nicht prim sein - fertig der Lack.

"PrimeQ[p] = False" ist demnach eine sichere Aussage, dass p nicht prim ist. Hingegen lässt "PrimeQ[p] = True" gemäß Mathematica-Hilfe nur den Schluß zu, dass p höchstwahrscheinlich (?!) eine Primzahl ist.
prim Auf diesen Beitrag antworten »

der hinweis kleiner fermat, war der für die überprüfung ob eine zahl eine primzahl ist ohne zerlegung(false,true) oder war es ein hinweis für mein anfangsproblem? weil für meine frage ist natürlich vorraussetzung das es keine primzahl ist. wie ich aber das gefühl habe gibt es wohl keine zahl die relativ klein sein wird. vom prinzip ist meine frage so eine art wettbewerb wer die kleinste zahl findet bei dem mathematica eine zerlegung nicht unter 10sek schafft. aber eine direkte methode als einfach zu probieren gibt es wohl nicht oder?...
JochenX Auf diesen Beitrag antworten »

danke arthur!

naja, zum eigentlichen problem kann ich leider nicht viel sagen, deswegen erlaubt mir noch folgenden satz bevor ich euch numeriker wieder unter euch lasse:

hallo prim! versuchs doch mal mit 42.
könnte aber sehr lange dauern die antwort dann....


edit: ! zu . verändert
ich meinte nicht fakultät, sondern nur 42
war ne anspielung auf den hitchhiker
prim Auf diesen Beitrag antworten »

ja 42! würde gehen aber da hab ich schon kleinere gefunden(was bei deiner zahl nicht schwer istAugenzwinkern ) die auch 10sek brauchen
AD Auf diesen Beitrag antworten »

Zitat:
Original von LOED
bevor ich euch numeriker wieder unter euch lasse:

Falscher Begriff, würde ich sagen: Numeriker beschäftigen sich eher mit Verfahren für reelle Zahlen, und den Unzulänglichkeiten, wenn Computer diese mit Binärmustern approximieren (Fehlerrechnung usw.).

Ich würde dann eher den Begriff Numerologe verwenden. Big Laugh
gast1 Auf diesen Beitrag antworten »

Zitat:
Original von prim
das kommt wohl auch noch dazu. aber vielleicht ist mein pc auch einfach zu schnellAugenzwinkern 10 sek ist bei mir nur mit sehr grossen zahlen zahlen hinzukriegen. aber vielleicht gibts ja besondere zahlen die nicht so einfach zerlegbar sind?????

Wie gesagt, wenn eine Zahl Produkt zweier großer Primzahlen ist, dauert es sehr viel länger, sie zu faktorisieren.
Vergleiche
14269215553763841061163*95598395807
und
2^10*3^34*5^20
Beide Zahlen haben 34 Stellen, doch das Faktorisieren der zweiten Zahl nimmt keine merkliche Zeit in Anspruch, während es bei der ersten Zahl auf meinem PC etwa 30 Sekunden dauert.
prim Auf diesen Beitrag antworten »

dürfte ich fragen was du für einen pc hast? ich benötige dafür gerade mal 4-6 sek.,aber ich habe schon verstanden was du damit sagen wolltest.
danke für eure hilfe.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »