Seite 1 von 1
Teiler von x
Verfasst: Donnerstag 10. September 2009, 22:00
von hendrikS
Wenn man nach Divisor googelt findet man einige smarte Formeln für die Anzahl der Teiler von x oder die Summe der Teiler. Eine Funktion, die die Divisoren zurückgibt habe ich nicht gefunden. Hier meine Lösung.
Code: Alles auswählen
from collections import defaultdict
from itertools import combinations
def primefactors(n):
pfs = defaultdict(int)
pf = 2
while pf ** 2 <= n:
if not n % pf:
n /= pf
pfs[pf] += 1
else:
pf += 1
if n > 1: pfs[n] += 1
return [(pf,count) for pf, count in pfs.iteritems()]
def divisors(n):
divisors = set()
pf = list()
for p,a in primefactors(n):
pf.extend([p]*a)
for i in xrange(1,len(pf)+1):
for j in combinations(pf,i):
divisors.add(reduce(lambda x, y: x*y, j))
return [1] + sorted(divisors)
print divisors(67679860)
Der Code läuft so nur mit 2.6, weil combinations erst ab 2.6 verfügbar. Ich habe es allerdings mit 2.5 entwickelt und mir die combinations Routine von hier
http://docs.python.org/library/itertools.html geklaut. Wenns Probleme gibt, kann ich auch noch mal den kompletten 2.5er Code irgendwo pasten.
Bei SPOJ oder projecteuler kann man damit allerdings keinen Blumentopf gewinnen. Die primefactors ist noch n'bissl lahm.
Verfasst: Freitag 11. September 2009, 06:20
von BlackJack
@hendrikS: Warum ist Zeile 14 so kompliziert? ``return pfs.items()`` hätte es doch auch getan!?
Re: Teiler von x
Verfasst: Freitag 11. September 2009, 07:17
von apollo13
hendrikS hat geschrieben:Bei SPOJ oder projecteuler kann man damit allerdings keinen Blumentopf gewinnen. Die primefactors ist noch n'bissl lahm.
Du könntest ja mal:
http://de.wikipedia.org/wiki/Sieb_des_Atkin probieren.
Verfasst: Freitag 11. September 2009, 07:22
von hendrikS
@BlackJack: Super, danke für den Tip. Hätte mir eigentlich nur die Beispiele aus der Hilfe etwas genauer ansehen müssen. Macht das ganze gleich auch wieder etwas schneller.
@apollo13: Die Siebe habe ich ganz weit oben auf der Agenda, weil sich ne ganze Menge von Problemen auf Primzahlen zurückführen lassen.
Re: Teiler von x
Verfasst: Freitag 11. September 2009, 13:24
von numerix
Wenn es darum geht, für einzelne Werte die Teilermenge zu bestimmen, dann ist ein Sieb nicht der richtige Weg, da man ja nicht alle Primzahlen bis zu einer bestimmten Grenze braucht, sondern nur die Primfaktoren einiger Zahlen. Dafür würde man ein effizientes Verfahren zur Primfaktorzerlegung einsetzen.
Inwieweit einem das gelungen ist, kann man hier ganz gut prüfen:
https://www.spoj.pl/problems/DIVSUM2/. Ohne effiziente Primfaktorzerlegung ist das nicht zu lösen.
Im übrigen ist das Sieb von Atkin deutlich aufwändiger zu implementieren als das Sieb des Eratothenes und ist unter dem Strich nur unwesentlich schneller.
Re: Teiler von x
Verfasst: Freitag 11. September 2009, 13:46
von apollo13
numerix hat geschrieben:
Wenn es darum geht, für einzelne Werte die Teilermenge zu bestimmen, dann ist ein Sieb nicht der richtige Weg, da man ja nicht alle Primzahlen bis zu einer bestimmten Grenze braucht, sondern nur die Primfaktoren einiger Zahlen. Dafür würde man ein effizientes Verfahren zur Primfaktorzerlegung einsetzen.
Ups stimmt. Ich denk immer wenn ich Primzahlen höre sofort ans sieb
