Wie viele Teiler hat eine Zahl?
lima-city → Forum → Sonstiges → Schule, Uni und Ausbildung
algorithmus
anwenden
berechnen
bereich
brauchen
erkennen
folgendes schema
gegenspieler
http
million
muster
nehmen
primzahl
problem
stelle
tabelle
takten
teiler
url
zahl
-
Hallo Leute.
Wie der Titel schon sagt, suche ich ein Verfahren das mir zeigt, wie viele Teiler eine Zahl hat (durch wie viele Zahlen x ohne Rest teilbar ist).
Eine Möglichkeit wäre alle Zahlen 1 - x/2 zu testen, und jedes mal 1+ zählen, falls x durch diese Zahl ohne Rest teilbar ist. Leider ist dies ganz schön lahm bei grossen Zahlen.
Die zweite Möglichkeit, die ich mir angeschaut habe, ist die Primfaktorzerlegung [http://de.wikipedia.org/wiki/Primfaktorzerlegung].
Dazu schaue ich, durch welche Primzahl die Zahl teilbar ist, und mache dann mit der geteilten Zahl weiter..
also so:
16 ist durch 2 teilbar..
also 16 = 2 * ..
--> 8 ist durch 2 teilbar
also 16 = 2 * 2 * ..
--> 4 ist durch 2 teilbar
also 16 = 2 * 2 * 2 * ..
--> 2 ist durch 2 teilbar
also 16 = 2 * 2 * 2 * 2
16 = 2^4
Das bedeutet, dass 16 insgesamt 4+1 = 5 Teiler hat.
Das Problem ist nur, dass ich für Zahlen von etwa 10^9 (Eine Milliarde) prüfen muss, wie viele Faktoren sie haben.
Für das benötige ich eine Primzahlentabelle bis 5*10^8 (also 500 Millionen). Das sind recht viele Primzahlen, man könnte sie zwar recht performant berechnen, aber im Endeffekt ist das zu langsam. Dazu käme dann noch der Speicherbedarf für die ganzen Primzahlen..
Mit andern Worten, dieses Verfahren ist für meine Ansprüche einfach nicht mehr gut genug.
Gibt es eine einfachere Möglichkeit, zu prüfen wie viele Teiler eine Zahl hat?
liebe grüsse
x-bLacK
-
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
-
Biste bei Project Euler am rumtüfteln?
An der Primzahlzerlegung wirst du nicht vorbeikommen. Aber sobald du diese hast, kannst du einfach folgendes Schema anwenden:
Gegeben eine Faktorzerlegung einer Zahl: z = a^A * b^B * c^C + ...
so ist die Anzahl der Divisoren: (A+1)*(B+1)*(C+1)*... -
Also ich glaube du wirst nich um eine Tabelle kommen...
http://de.wikipedia.org/wiki/Riemannsche_Vermutung
Dieses ist eines der aktuellen Millennium-Probleme...
Die Primfaktorzerlegenung wirst aber brauchen...
Gruß -
bladehunter schrieb: Biste bei Project Euler am rumtüfteln?
An der Primzahlzerlegung wirst du nicht vorbeikommen. Aber sobald du diese hast, kannst du einfach folgendes Schema anwenden:
Gegeben eine Faktorzerlegung einer Zahl: z = a^A * b^B * c^C + ...
so ist die Anzahl der Divisoren: (A+1)*(B+1)*(C+1)*...
Nicht Project Euler, aber so was ähnliches ;)
Ja das mit den Exponenten multiplizieren hab ich gemacht, diese Lösung funktioniert einwandfrei.
Das Problem dabei ist wie geschrieben, dass es eine Primzahltabelle voraussetzt. Diese zu berechnen würde zu viel Zeit benötigen, und wenn ich eine vorgerechnete als Array ins Programm speichere, hab ich locker so 300 MB sourcecode, und das ist natürlich nicht so optimal ;).
Geht es nicht irgendwie schneller und einfacher?
Möglicherweise so, dass ich nicht die Primfaktoren kennen muss?
Wie würde man eine Faktorzerlegung bei Zahlen machen, für dessen grössen noch keine Primzahlen gefunden wurden?
cube1983 schrieb: Also ich glaube du wirst nich um eine Tabelle kommen...
http://de.wikipedia.org/wiki/Riemannsche_Vermutung
Dieses ist eines der aktuellen Millennium-Probleme...
Die Primfaktorzerlegenung wirst aber brauchen...
Gruß
Danke, schau mir das mal an mit der Riemannschen Vermutung.
So wie ihr das sagt, ist das also nicht möglich ohne Primzahltabelle? -
ich hab zwar keine große Ahnung, höherer Mathematischer Verfahren, aber ich würde das Problem so angehen:
Vielleicht solltest du auch erstmal abgrenzen, bis zu welchen Bereich die zahl gehen kann in diesem Projekt... vermutlich bis maximal 8 Byte Speichergröße also 2^64 große zahlen.
Die Primfaktoren können also bis maximal 2^63 hoch gehen, gemäß, meine annahme stimmt, wobei x/2 die maximal erreichbare zahl ist.
Der Zahlenbereich ist natürlich nicht sinnvoll mit einem increment x algorithmus zu durchlaufen, denn die ausführungszeit auf einer maschine würde jahre brauchen. Es ist auch nicht mit einer Tabelle lösbar, die sämtliche möglichen Primzahlen als teiler enthält.
Wenn ich mir allerdings anschaue, dass bei einem Divisionsprozess, welchen man auf dem papier über eine spaltenverschobene Sutraktion realisiert, würde ich mir ein verfahren überlegen, bei dem ich direkt mit den Binärzahlen rechne. mit binärzahlen kann man wunderbar rechnen... man kann sie invertieren und über die binäraddition eine subtraktion realisieren. Ähnlich kann ich es mir vorstellen, dass man auf binärer Ebene einen Maskensatz anlegt, mit dem man Binärzahlen außerhalb der begrenzungen durch die 4 Grundrechenarten. Ich bin zwar kein Mathematiker, aber ich würde das nachprüfen. vielleicht ist es ein in der mathematik komplexeres Rechenmodell, aber in der IT simpel umsetzbar...
schließlich kann man im Dezimalen zahlensystem auch anhand der endziffern zum beispiel erkennen, ob eine zahl durch 2, 3, 5, 7, ... teilbar ist.
nehmen wir mal einen Zahlenbereich bis 100 an, bei dem 50 die maximale Zahl ist, können wir anhand der 1. stelle erkennen, ob die zahl durch 2 teilbar ist, wenn substring(x,-1,1) eine zahl aus der folgenden reihe ist {0, 2, 4, 6, 8}. im binären bereich würde es noch einfacher ablaufen, nämlich wenn die x0 stelle im speicherbereich nicht gesetzt, also 0 ist. daran orientiert wird aus einer für den rechner recht komplexen rechenaufgabe ein einfaches 1&& !(substring(x,-1,1)). Dürfte superschnell gehen.
wenn wir auf 3 prüfen, müssen wir dann den wenn substring(x,-2,2) auf die Muster 11, 01 und 10 abprüfen nachobigem schema...
wenn wir die 4 prüfziffer nehmen, sehen wir, dass sie die 2 enthält anhand unseres Musters...
bei der 5 (101) müssen dann müssen nur die Muster 0101 und 1010 abgeprüft werden auf den letzten stellen...
wenn man den algorithmus richtig in eine schleife packt, hat die CPU das teil in 5-10 takten verarbeitet, während wir auf Dezimaler Ebene etliche Takte mehr für diese Enfache aufgabe brauchen, weil wir eine komplexe aneinanderreichung von takten brauchen, um eben so eine division durchzuführen...
Wenn man das weiterführt, hat man in kürzester zeit sämtliche Primzahlen auf diese Zahl herausgefunden. natürlich würde man zeitgleich den gegenspieler ermitteln um den Suchbereich nach oben konsequent einzugrenzen... wenn man nun alle gegenspieler ermittelt hat. Die Primzahlen kann man sich parallel auch über diese Methode entwickeln, weil die einfach eine individuelle Maske je primzahl entwickelt. Dies würde den Programmablauf zwar verlangsamen und die Primzahlentabelle im Speicher anlegen, diese würde aber immer nur auf das entsprechende Problem angepasst werden. Im zweifelsfalle kann man den Prozess immer noch Parallelisieren auf 2 Kerne, wobei einer die Primzahlentabelle errechnet und der andere Kern die Berechnung durchführt... die primzahlentabelle kann man zurprogrammlaufzeit im Speicher vorhalten... zur not kann man beim Programmstart den algorithmus auf eine musterzahl anwenden, die einfach durchzurechnen ist und eine ausreichende startmenge an primzahlen vorhält, dass kleinere Abfragen sauber durchgehen...
Keine Ahnung, ob das bei der Lösungsfindung hilft... -
Wenn man so ein Problem hat, dann suchst man am besten erstmal nach einem bestehenden StackOverflow Thread und da haben wir doch gleich einen: Algorithm to calculate the number of divisors of a given number
Worum du auf jeden Fall nicht herumkommst ist eine Primfaktorenzerlegung. Und das ist hier natürlich das Problem. Ein Primfaktortest ist zwar mittlerweile in polynomischer Zeit möglich, eine Primfaktorenzerlegung ist hingegen deutlich aufwändiger.
Daher würde ich hier auch nichts selber implementieren, sondern eine fertige Bibliothek nutzen. In dem StackOverflow Thread wurde zum Beispiel neben dem Sieve of Atkins zum Selbstimplementieren auch PARI als fertige Library angeboten. Damit fährst du garantiert besser, wenn es um große Zahlen geht. (Wenn es aber wirklich nur um kleine Zahlen geht (du sprichst von 500 Millionen, dass sind sehr kleine Zahlen), dann kannst du dich aber vielleicht auch selber daran versuchen.)
Beitrag zuletzt geändert: 14.10.2010 19:17:45 von nikic -
Diskutiere mit und stelle Fragen: Jetzt kostenlos anmelden!
lima-city: Gratis werbefreier Webspace für deine eigene Homepage
