Primfaktoren finden
Neue Frage »

16.05.2010, 13:45 geo1 Auf diesen Beitrag antworten »
Primfaktoren finden
Meine Frage:
Hallo,

kann mir jemand die folgende Zahl in Primfaktoren zerlegen?
594198643019111317652731271555360408630205036008274487434566320256885807412
856398150712949602079855567093936227

Etwas gross, aber vielleicht schafft es ja jemand.

Meine Ideen:
Durch 3 ist es nicht teilbar - ich habe die Quersumme probiert
16.05.2010, 14:06 Duedi Auf diesen Beitrag antworten »

Da kannst du lange rechnen. Bei solchen langen Zahlen kannst du Jahrhunderte brauchen, bis man Primfaktoren findet (oder zeigt, dass sie prim sind). Genau deswegen funktioniert die sogenannte RSA-Verschlüsselung.
16.05.2010, 14:11 sulo Auf diesen Beitrag antworten »
RE: Primfaktoren finden
@Duedi, ich vermute, wir sollen hier mal kräftig durch den Kakao gezogen werden. Augenzwinkern

(Mit anderen Worten: Spam)
16.05.2010, 14:14 AD Auf diesen Beitrag antworten »

Nun ja, zumindest die zweite, kleinere der beiden Zahlen besitzt drei lediglich zweistellige Primfaktoren... smile
16.05.2010, 14:16 Iorek Auf diesen Beitrag antworten »

@Arthur, ich denke mal die Zahl soll als eine einzige Zahl gelten, sonst hätte die obere einen sehr leicht zu sehenden Primfaktor Augenzwinkern
16.05.2010, 14:16 sulo Auf diesen Beitrag antworten »

Ich dachte, es wäre eine einzige Zahl?

Zitat:
Original von geo1
.... die folgende Zahl ...


verwirrt
 Anzeige 
 
16.05.2010, 14:20 Equester Auf diesen Beitrag antworten »

Welche Bildschirmeinstellung hast du denn, Arthur? xD
Mit deiner Aussage kann man max. eine 6-stellige Zahl erhalten?
(Dachte ich zumindest :P)
16.05.2010, 14:21 AD Auf diesen Beitrag antworten »

Jaja, ich gebe mich geschlagen - meine Bildschirmeinstellungen... Big Laugh
16.05.2010, 14:21 Airblader Auf diesen Beitrag antworten »

Ich denke, Arthur hat das nur scherzhaft gemeint.

@ Equester

Er hat ja nicht gesagt, es gäbe nicht noch weitere Faktoren.

Edit: So kann man sich irren. Schade Arthur, so hättest du dich "retten" können. Big Laugh

air
16.05.2010, 14:21 Iorek Auf diesen Beitrag antworten »

Equester, 1674364561 hat auch nur 3 zweistellige Primfaktoren Augenzwinkern
16.05.2010, 14:28 Equester Auf diesen Beitrag antworten »

3 unterschiedliche :P...^^
16.05.2010, 14:30 Airblader Auf diesen Beitrag antworten »

hat auch nur drei zweistellige Primzahlen, hat aber ca. 13 Millionen Ziffern.

air
16.05.2010, 14:31 Iorek Auf diesen Beitrag antworten »

Airblade du Erbsenzähler (Augenzwinkern ), meine Zahl hat aber außer den 3 zweistelligen Primfaktoren keinen weiteren (verschiedenen) mehr.
16.05.2010, 14:32 Airblader Auf diesen Beitrag antworten »

Aber davon war ja nie die Rede. "Sie hat nur drei zweistellige Primfaktoren" heißt ja nicht, dass sie nicht auch noch weitere Primfaktoren haben darf, die mehr Stellen haben.

Bazinga. Big Laugh
Edit: Oder, in HIMYM-Sprache: "You have been lawyered". Augenzwinkern

air
16.05.2010, 14:51 AD Auf diesen Beitrag antworten »

Huch, da habe ich ja eine Diskussion ausgelöst. smile

Ich weiß nicht, was an meinen Matheboard-Einstellungen nicht stimmt, aber ich sehe trotz 1920 Pixel Bildschirmbreite (also eigentlich noch genug Platz) hier aber zwei Zeilen, die ich als zwei Zahlen missdeutet habe:

code: 
1:
2:

594198643019111317652731271555360408630205036008274487434566320256885807412
856398150712949602079855567093936227

Und ich habe oben nicht gesagt, dass diese drei zweistelligen Primfaktoren die einzigen Primfaktoren der Zahl 856398150712949602079855567093936227 sind, sondern dass die Anzahl der zweistelligen Primfaktoren gleich drei ist. Augenzwinkern


P.S.: Übrigens wird es in der Code-Umgebung

code: 
1:

594198643019111317652731271555360408630205036008274487434566320256885807412856398150712949602079855567093936227

korrekt als eine einzige Zeile dargestellt. verwirrt
16.05.2010, 14:55 Airblader Auf diesen Beitrag antworten »

Im Originalpost ist die Zahl bei mir auch auf zwei Zeilen verteilt. Das liegt lediglich an der Monitor-Auflösung. Im Code ist es eine Zeile, weil zum Einen die Ziffern kleiner sind und sich diese Umgebung zweitens anpasst und notfalls das Layout des Boards zerreißen würde (oder der Scrollbalken wird umgebungsintern angezeigt, weiß ich grad nicht).

Wenn ich jetzt das hier mache wirds im Originalpost wahrsch. wieder korrekt dargestellt:

air
16.05.2010, 14:57 sulo Auf diesen Beitrag antworten »

Wenn man auf edit geht und sich den Text anschaut, erkennt man, dass Geo1 die Zahl als langen Bandwurm geschrieben hat. Offenbar wurde beim Veröffentlichen ein Zeileinumbruch eingefügt, der 2 Zahlen erzeugt hat.

[attach]14693[/attach]

Geo1 hat es einfach übertrieben... Big Laugh
16.05.2010, 15:02 AD Auf diesen Beitrag antworten »

Zitat:
Original von Airblader
Das liegt lediglich an der Monitor-Auflösung.

Hmm, mein Screenshot sagt da was anderes:

[attach]14694[/attach]

Die Zahl müsste bequem auf eine Zeile passen. verwirrt

Ah ja, Windows 7x64, Firefox 3.6.3 ... wird langsam zu einer technischen Anfrage hier (also bei Bedarf bitte auslagern).
16.05.2010, 15:05 Airblader Auf diesen Beitrag antworten »

Okay, das ist merkwürdig. Wäre denkbar, dass das matheboard ab einer gewissen Zeichenlänge automatisch einen Umbruch einfügt (also unabhängig von der Auflösung), weil das noch aus Zeiten stammt, wo Auflösungen meist recht gleich groß waren.

So selten ist das nicht.

air
16.05.2010, 15:09 sulo Auf diesen Beitrag antworten »

Das ist kein Screenshot des Beitrages im Thread, ich bin vielmehr mit dem edit-Button in den Beitrag reingegangen und konnte ihn so sehen, wie ihn Geo1 aufgeschrieben hat (und habe das so festgehalten).

Die Tatsache, dass seine Zahl exakt die Länge des Antwortfeldes hat, entlarvt ihn meiner Meinung nach eindeutig als Spammer. Augenzwinkern
16.05.2010, 15:10 Airblader Auf diesen Beitrag antworten »

Ja, eben - der Umbruch entsteht erst im matheboard. Von daher wird das matheboard intern wohl diese Funktion verwenden.

air
16.05.2010, 15:14 AD Auf diesen Beitrag antworten »

Das macht Sinn, da nach genau 75 Ziffern umgebrochen wird. Vielleicht kann man ja darüber nachdenken, die fest kodierte 75 in eine Variable umwandeln, die der Nutzer hier

http://www.matheboard.de/usercp.php?action=options_change

nach Bedarf einstellen kann? Augenzwinkern
16.05.2010, 15:16 Airblader Auf diesen Beitrag antworten »

Noch sinnvoller wäre eine dynamische Anpassung. Solche Dinge müssen wirklich nicht vom User geregelt werden.

Wenn überhaupt, sollte die einzige Einstellung beim User sein, ob überhaupt unmgebrochen werden soll, oder ob er lieber einen Quer-Scrollbalken haben möchte. Augenzwinkern

air
16.05.2010, 15:31 Mystic Auf diesen Beitrag antworten »
RE: Primfaktoren finden
Zitat:
Original von geo1
Durch 3 ist es nicht teilbar - ich habe die Quersumme probiert


Ja, durch 5 auch nicht... Tatsächlich sind die Primfaktoren in der vollständigen Faktorisierung etwas größer... Big Laugh

16.05.2010, 15:39 sulo Auf diesen Beitrag antworten »
RE: Primfaktoren finden
Die Primfaktoren sind so seltsam ähnlich... verwirrt
Dann hat Geo1 doch nicht einfach wild in den PC getippt, sondern es steckt ein System dahinter.
16.05.2010, 16:03 Mystic Auf diesen Beitrag antworten »
RE: Primfaktoren finden
Zitat:
Original von sulo
Die Primfaktoren sind so seltsam ähnlich... verwirrt
Dann hat Geo1 doch nicht einfach wild in den PC getippt, sondern es steckt ein System dahinter.

Das war mir sehr schnell klar, denn dann hätte die Zahl mit einer sehr großen Wahrscheinlichkeit einen "kleinen" Primfaktor, mit sagen wir weniger als 10 Stellen haben müssen...Dagegen ist mir nicht klar, welche Absicht dahinter steckt... Sollte eine der gängigen Faktorisierungsmethoden damit demonstriert werden?...

In Frage kämen hier die Fermatsche Methode und die Pollardsche p-1-Methode... Z.B. gilt für

q :=4938521104504949308801118647

dass

FACTOR(q - 1) = 2*3*2791*972847*9364357*32371537069

d.h., das liegt gerade noch im Bereich des Machbaren... Für die Fermatsche Methode gilt Ähnliches...

P.S. Übrigens lag Duedi mit seiner Schätzung

Zitat:
Original von Duedi
Da kannst du lange rechnen. Bei solchen langen Zahlen kannst du Jahrhunderte brauchen, bis man Primfaktoren findet (oder zeigt, dass sie prim sind).

meilenweit daneben... Auch im worst case, wenn diese 111-stellige Zahl nur zwei etwa gleich große Primfaktoren gehabt hätte, hätte die Rechenzeit heute auf einem PC eher Tage/Wochen als Jahrhunderte betragen Big Laugh ...
16.05.2010, 16:17 sulo Auf diesen Beitrag antworten »
RE: Primfaktoren finden
Ich halte es nach wie vor für Spam. Und ich denke, wir sollten hier einfach mal an die Grenzen unserer Möglichkeiten geführt werden.

Wäre nett, wenn sich Geo1 mal wieder melden und uns über den Sinn seiner Anfrage aufklären würde.
16.05.2010, 23:04 kurellajunior Auf diesen Beitrag antworten »

Ihr seid immer noch großartig!
Gute Nacht und Danke für das Schmunzeln! Tanzen
17.05.2010, 10:35 geo1 Auf diesen Beitrag antworten »
Primfaktorzerlegung
Hallo,

ich melde mich leider erst sehr spät, weil ich jetzt erste eure Diskussion gelesen habe.
Nein, es ist kein spam, denn wie sollte da eine Zahl herauskommen, die aus vier
sehr ähnlichen Primzahlen zusammengesetzt ist. Natürlich wollte ich wissen, ob
die Zerlegung machbar ist. Das Produkt zweier der 4 Primfaktoren wurde bereits
im Matheformum diskutiert. Diese Zerlegung von nur 56-stelligen Zahlen scheint
erheblich schneller zu gehen als das ihres 111-stelligen Produktes, aber lösbar ist es
wohl, wie die Antwort zeigt.
Was die Zahlen sollen? Das ist ein geometrisches Problem - es geht darum herauszufinden, wo der Schnittpunkt der Linien ist, die zwischen den
Koordinatenpunkten liegen, die sie definieren.

Die Zahlen habe ich übrigens nicht im Fenster eingegeben, sondern von einem
Fenster (Maple) in das andere per copy paste gebracht. Dann gab es den Umbruch in der Darstellung automatisch.

geo1
17.05.2010, 11:00 sulo Auf diesen Beitrag antworten »
RE: Primfaktorzerlegung
Ist es also eine Geocaching-Aufgabe?


edit:
Tja, und da ist er wieder off.
Das fiel mir gestern abend noch ein, dass wir hier vermutlich mal wieder eine Geocaching-Nuss für jemanden geknackt haben...
Ob das jetzt so viel besser ist als Spam, weiß ich nicht.
17.05.2010, 11:19 Mystic Auf diesen Beitrag antworten »
RE: Primfaktorzerlegung
Zitat:
Original von sulo
Das fiel mir gestern abend noch ein, dass wir hier vermutlich mal wieder eine Geocaching-Nuss für
jemanden geknackt haben...

Ja, unter Berücksichtigung aller Umstände, insbesondere seines Nicknames, dürfte dies wohl zutreffen... unglücklich
17.05.2010, 11:58 geo1 Auf diesen Beitrag antworten »
RE: Primfaktorzerlegung
Nein,

1. wieso sollen Geocacher, die Fragen haben genauso schlimm sein wie spam?
Spam
2. Ihr habt mir keine Geocaching Nuss geknackt, sondern es ist umgekehrt.
Ihr knackt den Geocachern, die meine mathematischen Aufgaben gestellt bekommen, die Nüsse. Ich bin beeinduckt, dass es vorkommt, dass Ihr innerhalb von 5 minuten
schon die Lösung gebt, wenn die Frage an Euch gestellt werden.
Was dann schade ist, dass die ersten geocacher sich dann die Mühe machen, das
Rätsel selbst oder mit Eurer Hilfe zu lösen, dass dann spätere aber nur in Google
die zu zerlegende Zahl eingeben, um in Eurem Forum dann das Ergebnis zu bekommen. Das ist dann eher zu einfach - finde ich. Nach dem ersten mal habe ich daher (nicht ganz ohne Mühe) neue Primzahlen gesucht und später geht es
dennoch wieder mit Google! Wäre es denn möglich, die Zerlegung in Primfaktoren als Grafik einzugeben, damit es nicht zu einfach ist?

Ansonsten lade ich Euch gerne ein, mathematische Rätsel zu lösen, z.b. das:
http://www.geocaching.com/seek/cache_det...96-c32fef9571da

Nun aber noch mal die Frage nach der Zerlegung. Ich habe die Zahl, nach der ich gefragt habe, in factor.exe (ein gutes(?) dos-Programm) eingegeben und das
findet zwar nach einer kürzeren Zeit einen Faktor und das verbleibende Produkt ist damit deutlich kleiner. Aber es rechnet dann Stunden ohne Ende weiter.

Wie hat mystic es denn geschafft?
17.05.2010, 12:27 Mystic Auf diesen Beitrag antworten »
RE: Primfaktorzerlegung
Zitat:
Original von geo1
Wie hat mystic es denn geschafft?

Ich habe dazu ein selbstgeschriebenes Programme für die ECM verwendet, das nicht im freien Handel erhältlich ist... Im Nachhinein war dies für Primfaktoren dieser Größe auch erste Wahl...

Es gibt aber auch gute ECM- Programme im Internet, z.B. dieses hier...
17.05.2010, 14:29 geo1 Auf diesen Beitrag antworten »
RE: Primfaktorzerlegung
@mystic Alpertron kenne ich, damit hatte ich die Primzahlen ja berechnet.
Nur - es rechnet nicht sehr schnell mit dieser Zerlegung - ah, jetzt ist es nach
40 Minuten durch. Wie lange hat Dein Programm gebraucht?
17.05.2010, 15:27 Mystic Auf diesen Beitrag antworten »
RE: Primfaktorzerlegung
Zitat:
Original von geo1
@mystic Alpertron kenne ich, damit hatte ich die Primzahlen ja berechnet.
Nur - es rechnet nicht sehr schnell mit dieser Zerlegung - ah, jetzt ist es nach
40 Minuten durch. Wie lange hat Dein Programm gebraucht?


Eine knappe halbe Stunde...Ein Vergleich anhand dieses einen Beispiels ist allerdings schwer möglich, denn ich hatte die Schranke B1 für die erste Stufe von Anfang an auf 50000 gesetzt und auch sonst stimmen die Parameter für die einzelnen Kurven vermutlich nicht überein, d.h., es ist immer auch ein bißchen Glück dabei...

Edit: Für mich sieht das Ganze übrigens so aus, als hätte jemand (Geo1?) versucht ein Beispiel zu konstruieren, wo die Fermatsche Faktorisierungsmethode klappen sollte, was ihm aber letzlich mißglückt ist, da dazu die beiden Primfaktorren der Vielfachheit 1, obwohl bereits sehr nahe beieinander, noch immer zu weit auseinanderliegen...
17.05.2010, 21:33 geo1 Auf diesen Beitrag antworten »
RE: Primfaktorzerlegung
Zitat:
Original von Mystic
[quote]Original von geo1

Edit: Für mich sieht das Ganze übrigens so aus, als hätte jemand (Geo1?) versucht ein Beispiel zu konstruieren, wo die Fermatsche Faktorisierungsmethode klappen sollte, was ihm aber letzlich mißglückt ist, da dazu die beiden Primfaktorren der Vielfachheit 1, obwohl bereits sehr nahe beieinander, noch immer zu weit auseinanderliegen...


Ok, zugegeben, da ich diese Bemerkung nicht wirklich verstanden habe, kann ich auch nicht versucht haben, das zu konstruieren. Vielleicht war es fast ein Glückstreffer.

Das Rätsel bei Geocaching übrigens, was ich vor Jahren gestellt habe, hat sicher seitdem einige dazu bewegt, sich mit diesem Problem zu beschäftigen. So muss man deren Hobby wohl verstehen: Sie steigen kurzfristig in ein Rätsel ein, um diese Kiste zu suchen. Dabei geschieht es, dass man einen Mathematiklehrer im Haus anspricht und versucht, aus ihm die Lösung herauszubekommen. Und wenn das nicht klappt, dann geht man eben ins Matheboard und - aus Eurer Sicht - nervt dort etwas, weil bei all diesen Rätseln die Leute oft kommen. Die Bemerkung, dass Ihr das nicht mögt, weil dann die Rätselsteller von Euch verlangen, die Diskussion wieder zu löschen, ist durchaus berechtigt (aus beider Sicht). Aber dennoch: Bedenkt, dass durch solche Rätsel der eine oder andere "Mathemuggel" sich mit Mathematik beschäftigt. Umgekehrt gibt es einige mathematisch interessierte, die immer nur auf mathematischen Geocaches kommen.....
17.05.2010, 21:38 Airblader Auf diesen Beitrag antworten »

Die Lösung irgendwo zu erfragen hat nicht im Geringsten etwas mit Mathematik zu tun. Ebenso wenig kann man das Zerlegen in Primfaktoren als "Beschäftigung mit der Mathematik" bezeichnen.

Auf diese Art von Beschäftigung, nämlich Betrug, kann ich als Helfer jedenfalls verzichten.

air
17.05.2010, 22:29 Gualtiero Auf diesen Beitrag antworten »

Zitat:
Aber dennoch: Bedenkt, dass durch solche Rätsel der eine oder andere "Mathemuggel" sich mit Mathematik beschäftigt.

Was das betrifft, rennst Du bei uns offene Türen ein. Der Gedanke, Mathematik sozusagen ein wenig unter die Leute zu bringen, Interesse zu wecken und dem Schulfach Mathematik den Schrecken zu nehmen, spielt auf höherer Organisationsebene hier iim Matheboard sicher eine Rolle.

Den Grund, weswegen wir gegen GeoCaching-Rätsel allergisch sind, hast Du schon genannt: die Rätselersteller ärgern sich, dass ein mühsam erstelltes Rätsel, desen Lösung normalerweise ein, (zwei . . . ?) Stunden in Anspruck nimmt, in kürzester Zeit ergoogelt werden kann und nicht den Zweck erfüllt, für den es gedacht ist.

Insofern wundert es mich, dass Du als Rätselersteller die Sache so locker nimmst und bei uns eine Frage stellst. Dass jetzt GeoCacher bei ihrer Suche nach der Lösung auch bei uns fündig werden, kannst Du nur verhindern, indem Du keinen hier genannten Fachbegriff in Deinem Rätseltext verwendest. Aber nachdem Du uns von Deinem Vorhaben nicht von Anfang an in Kenntnis gesetzt hast, liegt in diesem Fall die Verantwortung bei Dir. Das wirst Du wohl einsehen, oder?
19.05.2010, 00:53 geo1 Auf diesen Beitrag antworten »

@gualtiero

einmal ganz von dem speziellen geocaching Problem abgesehen ist es offensichtlich, dass viele heute gar nicht mehr versuchen, sich selbst eine gewisse Expertise anzueignen, sondern einfach nur im Internet stöbern. Vermutlich gibt es keinen Weg, das zu verhindern. Das als "Betrug" zu bezeichnen ist deshalb anachronistisch - auch wenn es stimmen mag. Und bei dem Problem der Zerlegung von Primzahlen auf eigene Faust wird wohl praktisch niemand in der Lage sein, selbst Lösungen zu erarbeiten - jedenfalls nicht bei so grossen Zahlen. Es bleibt also nur der Weg, ein Programm im Internet zu suchen, mit dem das geht. Wenn man das hat, dann will ich schon hoffen, dass der eine oder andere damit etwas herumspielt und beim Lesen der Seiten - wenn sie gut gemacht sind - auch ein bisschen dazu lernt. So war das von mir gemeint, dass es doch einen positiven Effekt bringt und die Einstellung zur Mathematik in solchen Fällen verbessert. Wer eine 54 - stellige Zahl in ein, zwei Stunden selbst in Primfaktoren zerlegt, der wird wohl ein Genie sein.
Allergisch reagieren solltet Ihr also in Zukunft besser nicht, sonst schreckt Ihr noch jemanden ab.
19.05.2010, 07:31 Airblader Auf diesen Beitrag antworten »

Es ist aber ein Unterschied, ob jemand sich meldet und sich über die Theorie der Primfaktorzerlegung informieren will oder ob er ankommt, eine Zahl hinknallt und sie zerlegt haben will.
Nur letzteres ist hier nicht gern gesehen - und das ist nur die Gruppe Geocacher, die keine Lust hat, zu lernen, sondern lieber "betrügt".

air
Neue Frage »
Antworten »



Verwandte Themen

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


MatheBoard » Sonstiges » Rätsel & Wettbewerbe » Primfaktoren finden