[ZT] fast-quadratischer Teiler |
07.08.2016, 21:39 | Milbrae | Auf diesen Beitrag antworten » | ||||||||||
[ZT] fast-quadratischer Teiler (Könnte ein Admin bitte den Link einfügen? Danke ) Es geht darum, dass zu einer Zahl n die Zahlen a und b gefunden werden sollen, so dass gilt und die Differenz von a und b minimiert ist. Wenn n eine Quadratzahl ist, dann ist . Andernfalls ergibt sich für n = 60 bspw. a = 10, b = 6. Gesucht wird in dem Beispiel auf PP der fast-quadratische Teiler für n = 224403121196654400. Ich habe hierfür ein kleines Python-Programm gepostet:
Für solche Zahlen ist das Ergebnis mit der Routine nsd() relativ schnell zu berechnen. Wenn sich n aber wie folgt zusammensetzt: n = 2**3 * 3**2 * 5 * 7 * 11**2 * 23 * 67 * 73**2 * 83 * 89 * 97 * 101 * 103 * 107 = 1997176648439957666247720 ...brauche ich bereits ca. 26 Sekunden für die Berechnung, mit Pypy immerhin nur 6. Ich schätze, man kann die gesamte Operation immens beschleunigen, wenn man die Primfaktoren von n näher unter die Lupe nimmt. Ich weiß nur noch nicht genau wie. Meiner Meinung nach könnte man auch alle Teiler von n betrachten. 1997176648439957666247720 hat aber schon 110592 Teiler. Bei Zahlen mit noch mehr Primteilern bzw. größeren Primteilerpotenzen wächst diese Zahl schnell ins Unermessliche. |
||||||||||||
07.08.2016, 21:49 | Milbrae | Auf diesen Beitrag antworten » | ||||||||||
Für bessere Lesbarkeit habe ich das Programm minimal geändert:
|
||||||||||||
07.08.2016, 22:05 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||
Wohl wahr, zumal dann wenn man (wie bei dir) die Primfaktorzerlegung bereits kennt! Z.B. hat dein n "nur" Teiler - selbst wenn man die alle berechnet, ist man weit schneller als die von dir genannten Zeiten. |
||||||||||||
07.08.2016, 22:12 | Milbrae | Auf diesen Beitrag antworten » | ||||||||||
Wenn nicht HAL, wer sonst Das n mit gerade mal 110.592 Teilern ist zwar ein zeitaufwendigeres aber vielleicht auch ungeeignetes Beispiel. Es heißt ja immer "Think big!". Was also wenn n das Produkt der Primzahlen < 1.000 ist? Dann hätte n zwar nur 168 Primfaktoren, die läppern sich insgesamt aber zu 374.144.419.156.711.147.060.143.317.175.368.453.031.918.731.001.856 Teilern. Die alle zu prüfen wäre ganz schön ermüdend... |
||||||||||||
07.08.2016, 23:16 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||
Richtig, in dem Fall sollte man "intelligenter" vorgehen, also nicht alle Teiler betrachten. Wie auch immer, meine Anmerkung bezog sich ja auch nur auf den Vergleich zu deinem ersten Algorithmus. Und wie der sich bei "n das Produkt der Primzahlen < 1.000" verhält, darüber wollen wir wohl besser mal den Mantel des Schweigens decken. |
||||||||||||
07.08.2016, 23:19 | Milbrae | Auf diesen Beitrag antworten » | ||||||||||
Warum wollen wir das? |
||||||||||||
Anzeige | ||||||||||||
|
||||||||||||
07.08.2016, 23:20 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||
Das meinst du jetzt nicht ernst, oder? |
||||||||||||
07.08.2016, 23:24 | Milbrae | Auf diesen Beitrag antworten » | ||||||||||
Fehler gefunden. Wir wollen das wirklich nicht. Ich vermute, die "intelligentere" Variante hat mit der Primfaktorisierung zu tun. Für n = 1.000# sind das ja nur 168 Faktoren. |
||||||||||||
11.08.2016, 22:12 | Milbrae | Auf diesen Beitrag antworten » | ||||||||||
Auf ProgrammingPraxis gab's jetzt den Hinweis eines Nutzers zu einer Variante des Rucksack-Problems. Das Prinzip, warum das so ist, hab ich noch nicht ganz durchschaut. Das Haskell-Programm (wovon ich gar keine Ahnung hab), das er vorschlägt, scheint ganz gut zu funktionieren und gibt den Exponenten der e-Funktion zur Lösung wider. |
||||||||||||
11.08.2016, 22:49 | HAL 9000 | Auf diesen Beitrag antworten » | ||||||||||
Stimmt - logarithmiert ähnelt es dem Rucksackproblem. |
||||||||||||
13.08.2016, 14:45 | RavenOnJ | Auf diesen Beitrag antworten » | ||||||||||
Ich habe das Haskell-Programm des Users matthew in deinem Link etwas gepimpt. Die Funktion largestSubset gibt die Liste aus, die der geforderten Bedingung entspricht:
Laufzeit auf meinem ein paar Jahre alten Rechner (2 Kerne arbeiten parallel): 3 sec. Das Ergebnis: "primes =[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]" "target = 30.7931475747082, entspricht 23620771158595" "Summe logs Ergebnisliste: 30.793095488055403" "Ergebnisliste: [2,3,5,7,17,19,37,41,53,61,71]" "Produkt Ergebnisliste: 23619540863730" "Produkt Restliste: 23622001517543" "Produkt primes: 557940830126698960967415390" Edit: Für das Problem auf PP ergibt sich (Laufzeit 15 s; der große Laufzeitunterschied liegt an den zusätzlichen zwei Primfaktoren. Jeder weitere Faktor bringt eine Verdopplung des Baumes. 22 gegenüber 20 also ca. Faktor 4): "primes =[2,2,2,2,2,2,3,3,3,3,5,5,7,7,11,13,17,19,23,29,31,37]" "target = 19.976110238769248, entspricht 473712066" "Summe logs Ergebnisliste: 19.976023239718703" "Ergebnisliste: [37,31,23,19,7,5,3,3,3]" "Produkt Ergebnisliste: 473670855" "Produkt Restliste: 473753280" "Produkt primes: 224403121196654400" |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |
|