Faktorisieren

Ich weiß nicht ob man solche kleine Spiele hier posten draf aber wenn nicht kann das ja immer noch gelöscht werden...

Die Regeln

• Jedesmal wenn einer eine korekte faktorisierung geschaft hat darf er eine Zahl wählen die eine dezimalstelle mehr hat
• Ob eine Faktorisirung richtig ist ist warscheinlich leicht zu erkennen
• Das verwenden von Programmen ist erwünscht (natürlich)
• Faktorisiert wird auf alle Primfaktoren

Ich hoffe am ende wird sich ein leistungs starker Allogerithmus durch setzen

gut die erste zahl 95623164

Also ich finds ne nette Idee.

Meine Lösung: 95623164 = 22337131717101

Mein Algorithmus: Die Faktoren 2 und 3 erkennt man mit dem bloßen Auge, die 17 war dann geraten (Glück), die 101 dann offensichtlich, und der Rest trivial 😜

Und meine neue Zahl ist:

611003021

Ich hoffe ich hab alle Regeln richtig verstanden 😁
Und ich hoffe das Ergebniss meiner Zahl ist auch so schön, hab sie von meiner Maus abgetippt.

Hallo Traumzauberbaum,

so wie ich die Regeln verstanden habe, müsste deine neue Zahl jetzt 95623164 plus eine neue Stelle sein. Ok, so eindeutig ist das aber nicht.

herbivore

nö nö war schon richtig wie traumzauberbaum das gemacht hat

Original von Traumzauberbaum
Und meine neue Zahl ist:

611003021

Meine Lösung: 611003021 = 611003021 (= ist ne Primzahl)

Nächste Zahl: 1318530213

1318530213 = 3·3·7·11·13·19·7703

Neue Zahl: 84729023641

84729023641 = 31 * 167 * 1289 * 12697

Nächste Zahl: 313497387653

313497387653 = 37·8472902369

Neue Zahl: 3958282047720

Btw, wäre es die Idee, dass man das verwendete Programm selber geschrieben hat? "Mein" Algorithmus ist zweifelsfrei leistungsstark, aber ich habe ihn nicht selber geschrieben, ja nicht mal selber kompiliert ...

Hallo,
3958282047720 = 2·2·2·3·5·7·7·11·13·4707533

Neue Zahl: 39582820477407

3958282047720 = 3·13194273492469

Neue Zahl: 392856483920471

@cdr: Benutze auch kein eigenes Programm momentan, denke mal interessant wirds erst wenn die Zahlen größer werden - wenn dann Standardlösungen versagen komms wieder auf unseren Gehirnschmalz an 😉

392856483920471 = 2221*176882703251

Nächste Zahl: 3402316736605866

@talla: Ok ... nun, bis gut 100 Stellen ist meine Standardlösung noch dabei 😉

3402316736605866 = 2·3·73·114407·67896601

Nächste Zahl: 84926381637549237

84926381637549237 = 3 * 23 * 373 * 49459 * 66717439

Fast Forward: 74270893012585041013206443057515

(Oder 742708930125850410 für kleinere Schritte)

alter schwede ich hab von anfang an gedacht das es hier um selbst programmiertes geht. hab jetzt ein Programm geschrieben, aber bis ergebnisse fertig sind, habt ihr ja schon wieder gepostet 🙁

Also bis zu cdrs Fast Forward bringt mein selbstgeschriebenes Programm die Antwort fast sofort.
Interessant dabei ist: Ich weiß ganz genau, dass in dem Programm ein Fehler ist, aber es bringt bisher trotzdem die richtigen Ergebnisse 😁

Ok, dann hab ich wohl eine interessante Grenze überschritten ... etwa 2^64?

Macht sonst mit der kleineren Zahl weiter, die ist noch als UInt64 speicherbar 😉

Nö das ist nicht das Problem. Schlau wie ich bin hab ich das Programm gleich in Python geschrieben, was ja mit beliebig großen Zahlen umgehen kann.
Es dauert mir nur zu lange, und weil noch ein kleiner Fehler drin ist, kümmer ich mich erstmal um den bevor ich es länger laufen lasse 😜

Original von cdr
84926381637549237 = 3 * 23 * 373 * 49459 * 66717439

Fast Forward: 74270893012585041013206443057515

(Oder 742708930125850410 für kleinere Schritte)

Die kleine kann ich ja jetzt relativ schnell mit meinem Algorhitmus berechnen, aber mit der großen hab ich Probleme, da sie selbst für "decimal" das mit 28 klar kommt zu groß ist.

Wie realisiert man solche Übergroßen Zahlen?

Hallo xxxprod,

==> BigInt

herbivore

Hallo,
hier mal ne kleine Anleitung um Primfaktoren zu erstellen:

Mit dem Sieb des Eratosthenes erstellt ihr eine Liste sagen wir mal mit den Primzahlen von 1 bis 100 Millionen.

Dann zur Faktorisierung:

n = 1 //Am Anfang die erste Primzahl aus der Liste nehmen, also die 2
Laufe solange, wie die Zahl größer als 1 ist:
   Lässt sich die Zahl durch die n. Primzahl (in der Liste) ohne Rest teilen?
      Ja: Primfaktor gefunden. Zahl hierdurch teilen
      Nein: n um 1 erhöhen

Wo man aufpassen muss, ist wenn die n. Primzahl nicht mehr in der List vorhanden ist. Hierdrauf muss man reagieren, und dann die nächste Primzahl "on the fly" berechnen und der List hinzufügen.

Bis 100Millionen du bist lustig xD
Als ich noch in Basic Programiert hab hab ich mal ein programm geschrieben das hab ich 2 Tage laufen lassen um möglichst viele Primzahlen zu finden und das ist in den 2 Tagen nicht über 7Millionen gekommen Und das war ein virtel gigabyte die datei war so groß das ich probleme hatte sie zu löschen (ich glaub die hab ich bis heute nicht gelöscht)

Mit dem Sieb des Eratosthenes braucht man auf jeden Fall ziemlich lange um die zu finden.

Ich hatte etwas ähnliches gemacht, nur noch optimiert mit probabilistischen Primzahltests, und einem viel früherem Ende.
D.h. ich hab getestet, ob die Zahl eine Primzahl sein könnte. Mit ner sehr kleinen Wahrscheinlichkeit erwisch ich dann auch mal eine Zahl, die keine Primzahl ist, und versuche mit der zu teilen. Das liefert nie eine falsche Faktorisierung, macht aber etwas Extraaufwand für den Divisionsversuch. Wobei der Aufwand wohl kleiner ist als das Aussieben der Pseudoprimzahlen 😉
Für cdrs Zahl ist das aber deutlich zu langsam.

In ner Woche hab ich die schlimmsten Prüfungen weg, dann schau ich mir das nochmal an.

Aber vielleicht sollte man doch selbst prgramierte alogerithmenverwenden denn irgentwie ist das langweilig wenn man ein programm von einem profi mathematiker hat, da geht der spaß auch ziemlich schnell flöten

Hallo Nopileos,

tja, das ist aber schwierig zu prüfen. Außerdem, wo ist der Unterschied, wenn man Algorithmus von einem Profi-Mathematiker in ein eigenes Programm umsetzt? Denn dass man hier ohne die erforschten Algorithmus, mit einem eigenen oder gar naiven Ansatz weit kommt, glaube ich nicht. Dazu sind Primzahlen ein zu gut erforschtes Gebiet.

herbivore

Hallo,

Original von Nopileos
das hab ich 2 Tage laufen lassen um möglichst viele Primzahlen zu finden und das ist in den 2 Tagen nicht über 7Millionen gekommen

Dann ist dein Programm/Algorithmus extrem schlecht programmiert.

Traumzauberbaum
Mit dem Sieb des Eratosthenes braucht man auf jeden Fall ziemlich lange um die zu finden.

Also meine C# Implementierung des Algorithmus (Sieb des Eratosthenes) braucht für die Berechnung der Primzahlen 2 bis 100 Millionen ca. 5 Sekunden (2 Ghz Rechner) und dabei ist er nicht besonderns optimiert für große Listen mit Primzahlen.
Man kann ihn noch weiter optimieren und so eine Liste mit den Primzahlen 2 bis 1 Mrd. in 13 Sekunden erstellen. Dazu muss man aber schon viel mit dem Speicher "rumfuchsen", denn sonst benötigt die anfänglich generierte Liste bis zu 1 GB Speicher, sofern jede Speicheradresse für 1 Zahl stehen soll..

Damit die Laufzeit aber nicht explodiert, muss man das Sieb möglichst effizient gestalten, sprich es soll keine unnötigen (doppelten) Produkte bilden sondern mit der Mindestanzahl an Produkten auskommen.

Eine nette Abhandlung dazu findet ihr hier:
Das Sieb des Eratosthenes <span style="font-size: 10;">(Wie schnell kann man alle Primzahlen bis eine Milliarde berechnen?)</span>

Danke Herbivore hab diese Klasse eingebunden und funktioniert ganz gut.

Was jetzt noch interessant wäre, ist wie man die Berechnung in verschiedene Threads auslagern könnte um so Multiprozessorkerne auslasten zu können.

Hat da wer Tipps dazu vielleicht?

Original von Qwald
Hallo,

Original von Nopileos
das hab ich 2 Tage laufen lassen um möglichst viele Primzahlen zu finden und das ist in den 2 Tagen nicht über 7Millionen gekommen
Dann ist dein Programm/Algorithmus extrem schlecht programmiert.

Beleidige nicht meine Alogerithmen, das das so lahm war liegt daran das ich da a 12 War und b das Qbasic in der Version von 81 war

@Qwald

Das Problem ist, dass ich weder 1GB Ram habe, noch 2 Ghz und 10^9 wahrscheinlich sowieso nicht ausreicht für eine 32 Stellige Zahl.

Sind 1GB nicht 1.000.000.000 Byte (eine milliarde)? bei 1 milliarde zahlen ist die größte zahl doch 30 bit lang, das passt do nie im leben!

Aber könnte man nicht Stück für stück die tabelle erweitern? und immer 1MIllion zahlen in eine tabell packen die Primzahlen ermitteln die Tabelle dann in eine endablage schreiben und bei verwenden der nächsten Tabelle hinzuziehen?

Original von cdr
84926381637549237 = 3 * 23 * 373 * 49459 * 66717439

Fast Forward: 74270893012585041013206443057515

(Oder 742708930125850410 für kleinere Schritte)

Ich geh mal die kleineren Schritte weiter, da mein Pgm sich beim großen übergibt^^

23515115710079103610399=742708930125850410

Meine Zahl: 3452682375741945294

Für Primzahlen bis zu 63Bit (rund 9.2 Trillionen): [KLASSE]Primzahlen und Integers

Hallo,

Original von Nopileos
Beleidige nicht meine Alogerithmen, das das so lahm war liegt daran das ich da a 12 War und b das Qbasic in der Version von 81 war

Ja dann Entschuldigung. Aber selbst mit Brute Force schafft man Primzahlen bis 10 Millionen relativ schnell (paar Minuten). Hab mich halt doch sehr gewundert.

@Nopileos:
Beim Sieb des Eratosthenes erstellt man zuerst eine List, in der man alle Zahlen notiert (z.B. von 2 bis 1 Mrd). Danach löscht man alle nicht Primzahlen aus der Liste.
Allerdings schreibt man nicht wirklich die Zahlen in die Liste, denn bei 32 Bit Zahlen wären das dann 32 GB Speicher, sondern man erstellt ein bool-Array mit 1 Mrd. Elemente. Wenn der Wert auf true steht, ist es eine Primzahl, sonst nicht (man kann es auch anders rum machen). Dann beim Löschen der Produkte (der nicht Primzahlen) setzt man den Wert von true auf false.
Dabei ist der Index die entsprechende Zahl. Also das 2. Elemente würde für die Zahl 2 stehen und das 1000. Element für die Zahl 1000 usw.
Da bool nur einen Speicherbedarf von 1 Byte hat, braucht man für Primzahlen bis 1 Mrd. auch "nur" 1 GB Speicher.

Bei Zahlen bis 100 Mio. ist der Speicherbedarf nur 100 MB, was nocht akzeptabel ist (durch am Anfang auslassen aller geraden Zahlen kann man den Speichbedarf auf 50 MB senken)

Für Primzahlen bis 1 Mrd. wäre es aber weiterhin zu viel. Deswegen verwendet man dann Bits, die angeben, ob eine Zahl prim ist oder nicht. Dazu braucht man dann nur noch 125 MB für die am Anfang erstellte Liste. Da man aber (leider) keine Bits direkt adressieren kann, muss der Code einige Bit-Manipulationen enthalten, was natürlich den Programmieraufwand erhöht.

Für Primzahlen bis 1 Mrd. wäre es aber weiterhin zu viel.

Die oben von mir verlinkte Klasse umgeht dieses Problem, indem sie immer blockweise das Sieb anwendet. Da die Primzahlen sowieso gesichert werden müssen, wird ein abgeschlossener Block in eine Datei geschrieben. Aus dieser werden auch bekannte Primzahlen für jeden weiteren Block geladen. Das setzt zwar die Rechengeschwindigkeit herab, lässt sich aber dafür kontinuierlich im Hintergrund ausführen, da der Speicherbedarf konstant ist.

Momentan nutzen die Klassen long als Zahlenformat.
Falls das jemand auf BigInt anpassen möchte, nur zu...

Original von Qwald
Für Primzahlen bis 1 Mrd. wäre es aber weiterhin zu viel. Deswegen verwendet man dann Bits, die angeben, ob eine Zahl prim ist oder nicht. Dazu braucht man dann nur noch 125 MB für die am Anfang erstellte Liste. Da man aber (leider) keine Bits direkt adressieren kann, muss der Code einige Bit-Manipulationen enthalten, was natürlich den Programmieraufwand erhöht.

Kannst du vielleicht erklären wie sowas aussehen könnte, oder wonach ich da suchen sollte?

Hab jetzt wahrscheinlich einen ähnlichen Algorhitmus integriert der ziemlich schnell ist, aber bei mehr als 1Mrd geht mir der Speicher aus.

Hallo,
also man kann es z.B. mit Dateien lösen. Du erstellst eine Datei (oder ein Array) in die du 1 Mrd. Bits schreibst, z.B. 1 für Prim und 0 für Nicht Prim, dann schreibst du also 125 Millionen mal 0xFF in die Datei/ins Array.

Danach musst du es hinbekommen, einzelne Bits auszulesen. Dafür musst du zuerst errechnen, in welchem Byte das Bit vorhanden ist, da man ja nur Bytes auslesen kann.
Man kann dazu dann einfach die Nummer des Bits durch 8 teilen. Wenn du also gucken möchtest, ob die Zahl (Bit) 17 eine Primzahl ist, teilst du 17 durch 2 macht dann das 3. Byte (bzw. Index 2).

Dies kann in etwa so aussehen:

byte GetByteForBit(int n)
{
    return byteArray[n/8];
}

Danach musst du feststellen, welches Bit es in dem Byte ist. Dies geht über Rest (bzw. Differenz), also 2*8 = 16 und zu 17 ist die Differenz 1, also das Bit mit dem "Index" 1 (hier wird davon ausgegangen, dass das Bit ganz rechts den Index 0 hat).

Auslesen kann man es ca. so:

int BitInByte(byte b, int diff)
{
    return (b & Math.Pow(2, diff));
}

Die Rückgabe ist dann entweder 0 (was nicht prim bedeutet) bzw. größer 0 (genau 2^(diff))

Ganz kann die Funktion z.B. so aussehen:

bool IsPrim(int n)
{
   byte b = byteArray[n/8];
   int diff = n%8;

   if( (b & Math.Pow(2, diff)) > 0) //Hier muss Math.Pow() noch auf int gecastet werden
     return true;
   else
     return false;
}

Ändert man jetzt eine Zahl von prim auf nicht prim, muss das ganze rückwärts ablaufen, also du musst wieder die Position des Bits herausfiltern und dann das Bit auf 0 setzen.
Sollte dir der Schreibvorgang noch Probleme bereiten, solltest du dich mal über Bit-Manipulation informieren, also wie man einzelne Bits ausliest bzw. ändert (auf pronix.de gibts eine Abhandlung in C darüber (im Buch C von A bis Z))

Falls man noch etwas optimieren* möchte:

Math.DivMod berechnet n/8 und n%8 gleichzeitig. Bei früheren Architekturen war ausserdem "n>>3" schneller als "n/8", und "n&0x7" schneller als "n%8", gilt afaik heute aber nicht mehr.

Statt "Math.Pow(2, diff)" ist aber wahrscheinlich "1<<diff" etwas schneller.

detail: statt "if(cond) return true; else return false;" kann man auch einfach "return cond;" schreiben, aber ich schätze der compiler optimiert das ohnehin weg.

*müsste man aber immer profilen, nicht immer ist was schneller aussieht auch wirklich schneller; je besser der compiler je weniger ...

Original von xxxprod

Original von cdr
84926381637549237 = 3 * 23 * 373 * 49459 * 66717439

Fast Forward: 74270893012585041013206443057515

(Oder 742708930125850410 für kleinere Schritte)

Ich geh mal die kleineren Schritte weiter, da mein Pgm sich beim großen übergibt^^

23515115710079103610399=742708930125850410

Meine Zahl: 3452682375741945294

Mein Faktorisierprogramm (ja ich habe jetzt nach 3 Tägigem kurzUrlaub fertig gemacht) hat mir 233*13 rausgeworfen danach waren leider noch 14755052887786091 übrig ich hab jedoch nach allen Primzahlen zwischen 2 und 400000000 gesucht , angenommen 14755052887786091 wäre keine Primzahl wär der größte möglichste kleinere Primfaktoren die wurzel aus 14755052887786091 (~121470379) da ich zahlen in dieser größenordnung gesucht hab gehe ich davon aus das 14755052887786091 eine Primzahl ist also
2 * 3 * 3 * 13 * 14755052887786091 = 3452682375741945294

neue Zahl (in anlehnung an cdr) : 74270893012585041013

Du hast richtig gefolgert, 14755052887786091 ist prim.

Ich werde wohl mal aussetzen, wäre wohl zu billig mit dem fertigen tool gegen eure selbstgeschriebenen algos anzutreten. Hatte übrigens Maple verwendet:

> with(numtheory):
> isprime(14755052887786091)     -> true
> ifactor(3452682375741945294)     -> (2) (3)^2 (13) (14755052887786091)

Maple implementiert übrigens den "Morrison-Brillhart" Algorithmus (man kann durch einen Parameter aber auch andere Algorithmen wählen: "D. Shanks' undocumented square-free factorization", "J.M. Pollard's rho method" und "Lenstra's elliptic curve method"). Google findet diverse Papers dazu...

Ja ich versuch gerade den quadratic sieve zu implementieren. Ich scheiter noch am letzten Schritt, irgendwie krieg ich immer 2 gleiche Wurzeln raus 🙁
Aber kommt bestimmt bald 😉

Original von Nopileos

Original von xxxprod

Original von cdr
84926381637549237 = 3 * 23 * 373 * 49459 * 66717439

Fast Forward: 74270893012585041013206443057515

(Oder 742708930125850410 für kleinere Schritte)

Ich geh mal die kleineren Schritte weiter, da mein Pgm sich beim großen übergibt^^

23515115710079103610399=742708930125850410

Meine Zahl: 3452682375741945294

Mein Faktorisierprogramm (ja ich habe jetzt nach 3 Tägigem kurzUrlaub fertig gemacht) hat mir 233*13 rausgeworfen danach waren leider noch 14755052887786091 übrig ich hab jedoch nach allen Primzahlen zwischen 2 und 400000000 gesucht , angenommen 14755052887786091 wäre keine Primzahl wär der größte möglichste kleinere Primfaktoren die wurzel aus 14755052887786091 (~121470379) da ich zahlen in dieser größenordnung gesucht hab gehe ich davon aus das 14755052887786091 eine Primzahl ist also
2 * 3 * 3 * 13 * 14755052887786091 = 3452682375741945294

neue Zahl (in anlehnung an cdr) : 74270893012585041013

Bei der Zahl hatte ich wohl glück^^ 2919335039*262932599731=74270893012585041013

PS: bin noch am Optimieren meines Codes für die ultimative Performance.. und Speicherverwaltung^^

Neue Zahl ist 742708930125850410137

Kann es sein das bool den Speicher "missbraucht"?
Wenn ich mein Programm starte steigt die auslagerungs datei um etwas mehr als 400 MB obwohl ich nur 400 Millionen Bool verwende daraus würde eingentlich 400Mb => 50 MB folgen, Kann ich eigentlich spei her sparen wenn ich ein Byte array verwende und die bytes dann in bool umrechne?

Original von Nopileos
Kann es sein das bool den Speicher "missbraucht"?
Wenn ich mein Programm starte steigt die auslagerungs datei um etwas mehr als 400 MB obwohl ich nur 400 Millionen Bool verwende daraus würde eingentlich 400Mb => 50 MB folgen, Kann ich eigentlich spei her sparen wenn ich ein Byte array verwende und die bytes dann in bool umrechne?

Original von Qwald
Hallo,
also man kann es z.B. mit Dateien lösen. Du erstellst eine Datei (oder ein Array) in die du 1 Mrd. Bits schreibst, z.B. 1 für Prim und 0 für Nicht Prim, dann schreibst du also 125 Millionen mal 0xFF in die Datei/ins Array.

Danach musst du es hinbekommen, einzelne Bits auszulesen. Dafür musst du zuerst errechnen, in welchem Byte das Bit vorhanden ist, da man ja nur Bytes auslesen kann.
Man kann dazu dann einfach die Nummer des Bits durch 8 teilen. Wenn du also gucken möchtest, ob die Zahl (Bit) 17 eine Primzahl ist, teilst du 17 durch 2 macht dann das 3. Byte (bzw. Index 2).

Dies kann in etwa so aussehen:

  
byte GetByteForBit(int n)  
{  
    return byteArray[n/8];  
}  

Danach musst du feststellen, welches Bit es in dem Byte ist. Dies geht über Rest (bzw. Differenz), also 2*8 = 16 und zu 17 ist die Differenz 1, also das Bit mit dem "Index" 1 (hier wird davon ausgegangen, dass das Bit ganz rechts den Index 0 hat).

Auslesen kann man es ca. so:

  
int BitInByte(byte b, int diff)  
{  
    return (b & Math.Pow(2, diff));  
}  

Die Rückgabe ist dann entweder 0 (was nicht prim bedeutet) bzw. größer 0 (genau 2^(diff))

Ganz kann die Funktion z.B. so aussehen:

  
bool IsPrim(int n)  
{  
   byte b = byteArray[n/8];  
   int diff = n%8;  
  
   if( (b & Math.Pow(2, diff)) > 0) //Hier muss Math.Pow() noch auf int gecastet werden  
     return true;  
   else  
     return false;  
}  
  

Ändert man jetzt eine Zahl von prim auf nicht prim, muss das ganze rückwärts ablaufen, also du musst wieder die Position des Bits herausfiltern und dann das Bit auf 0 setzen.
Sollte dir der Schreibvorgang noch Probleme bereiten, solltest du dich mal über Bit-Manipulation informieren, also wie man einzelne Bits ausliest bzw. ändert (auf pronix.de gibts eine Abhandlung in C darüber (im Buch C von A bis Z))

hab jetzt auch auf byte-Arrays umgestellt, da bool arrays den selben speicher belegen(warum eigentlich). Kostet allerdings etwas performance weil dauernd umgerechnet werden muss...

Probierts doch mal mit BitArray. Das ist für solche Dinge gedacht.

Das kannte ich bisher nicht, werd ich daher gleich mal ausprobieren.

Hallo,
742708930125850410137 = 1163 * 538697 * 1185480389267

Neue Zahl:
5615723048214631462487

131074037184074920655257=5615723048214631462487

Hat nur ein paar Stunden gedauert die neue zu berechnen^^
Neu: 79878234793842394838832

Hallo,
79878234793842394838832 = 2 * 2 * 2 * 2 * 3 * 97 * 17155978263282301297 (Faktorisiert in 0,015 Sekunden)

Neu: 624667279310247843579213 (Zerlegbar in 0,06 Sekunden)

33109597*633297220534471081=624667279310247843579213

hat bestimmt keine 0.06 sec gedauert aber ich bin ja mit meinem PGM noch lang nicht fertig^^

Hier mal das nächste: 8429392348729387566299384