Teiler von x

Code-Stücke können hier veröffentlicht werden.
Antworten
Benutzeravatar
hendrikS
User
Beiträge: 420
Registriert: Mittwoch 24. Dezember 2008, 22:44
Wohnort: Leipzig

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.
BlackJack

@hendrikS: Warum ist Zeile 14 so kompliziert? ``return pfs.items()`` hätte es doch auch getan!?
apollo13
User
Beiträge: 827
Registriert: Samstag 5. Februar 2005, 17:53

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.
Benutzeravatar
hendrikS
User
Beiträge: 420
Registriert: Mittwoch 24. Dezember 2008, 22:44
Wohnort: Leipzig

@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.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

apollo13 hat geschrieben:Du könntest ja mal: http://de.wikipedia.org/wiki/Sieb_des_Atkin probieren.
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.
apollo13
User
Beiträge: 827
Registriert: Samstag 5. Februar 2005, 17:53

numerix hat geschrieben:
apollo13 hat geschrieben:Du könntest ja mal: http://de.wikipedia.org/wiki/Sieb_des_Atkin probieren.
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 ;)
Antworten