Project Euler 21

[nemomuk]

Hallo,

habe gerade aus Langeweile versucht Problem 21 von Project Euler zu lösen:

Code: Alles auswählen

total = 0
for i in xrange(1, 10000):
    result = sum([j for j in xrange(1, i/2+1) if i % j == 0])
    if sum([j for j in xrange(1, result/2+1) if result % j == 0]) == i:
        total += i
print total

Irgendwie stehe ich gerade auf dem Schlauch oder habe das Problem falsch verstanden... auf jeden Fall kommt nicht das raus, was raus kommen soll.

Kann mir da jemand einen "Tipp" geben...?^^

[BlackJack]

@SchneiderWeisse: Du hast den selben Fehler gemacht, wie jemand anders, der das Thema hier im Forum schon einmal gebracht hat. → Suchfunktion.

[ms4py]

Meine Tipps:
- die Funktion d(n) cachen
- itertools.combinations verwenden

Hab damit ca. 30s gebraucht.

[nemomuk]

Danke @ BlackJack... hatte ich übersehen.

@ice2k3: Erstens geht es mir nicht um Performance, solange es nicht zu lange dauert und zweitens braucht meine Version 8s... (dennoch danke für die Tipps, auch wenn mir itertools durchaus bekannt sind)

[BlackJack]

@SchneiderWeisse: Das kommt ganz auf den Rechner an. Schau Dir in dem anderen Thread mal die Zeiten an, die ich auf dem C64 in BASIC mit so einem naiven Ansatz gebraucht habe.

[ms4py]

``combinations`` ist in diesem Fall natürlich voll der overload...
Hatte irgendwie einen Denkfehler

(Komm jetzt auf 3s )

[BlackJack]

Booah dauert das lange. 0.125 s sinds bei mir. Dabei habe ich jetzt die C64-BASIC-Lösung wieder nach Python rückübersetzt.

Tipp: Man muss die "teuren" Operationen wie Division eliminieren. Der ganze Code macht nur noch eine einzige (insgesamt!) davon. Und das auch noch durch 2, dass heisst bei einer "nativ" kompilierten Sprache könnte der Compiler das sogar zu einer Shift-Operation optimieren. Bzw. sogar schon zur Übersetzungszeit ausrechnen.

[nemomuk]

Ja, ich hatte den Thread gesehen, vllt. versuch ich mich auch an einer Rückübersetzung deiner Lösung, aber da müsste mir schon sehr langweilig sein...

[BlackJack]

@SchneiderWeisse: Das wird nicht soviel bringen, denn in dem anderen Thread steht ja noch die langsame, naive Variante, die auf dem C64 3h 40m gebraucht hat, und nicht die "schnelle", die "nur" 15½ Minuten braucht. Im letzten Beitrag dort von mir ist ein Hinweis, wie die Lösung aussieht.

Hab das mal nach C portiert, da braucht der C64 jetzt nur noch 14 Sekunden.

[pillmuncher]

Booah dauert das lange. 0.125 s sinds bei mir.

Danke für den Hinweis mit der Division, dadurch sind es jetzt 0.050 s bei mir . Vorher dauerte es 6.5 mal so lang. Erst hab ich ja nicht so recht gewusst, was du meinst, aber dann ist mir dieses Gedicht unbekannten Ursprungs wieder eingefallen:

Sieve the twos and sieve the threes -
The sieve of Eratosthenes!
When the multiples sublime
The numbers which remain are prime!

Ich wusste nicht mehr ganz genau wie es geht, deswegen hab ich es gegoogelt und dabei noch dies hier gefunden:

I've factored large numbers,
I've factored small,
Sooner or later,
I'll factor them all.

-- Scott Contini

Gruß,
Mick.

[Hyperion]

Oha... Mathe-Lyric - ist ja grauenvoll

[numerix]

Falls jemand weiterhin das Bedürfnis verspürt, sich mit der Berechnung von Teilersummen zu beschäftigen und dabei Wert auf gute Laufzeit legt, kann er sich hiermit vergnügen (und messen ....):
Nicht so schwer: https://www.spoj.pl/problems/DIVSUM/
Nicht so einfach: https://www.spoj.pl/problems/DIVSUM2/

[pillmuncher]

Oha... Mathe-Lyric - ist ja grauenvoll

Und das erst: http://www.trurl.net/gedicht.html

Gruß,
Mick.

[nemomuk]

Komme mit meiner Lösung auf 0.07 Sekunden, die an BlackJacks Lösung angelehnt ist...

[pillmuncher]

Meine braucht bei mir 0.047 s. (Python 2.6.4, WinXP, Intel T6570 2.1GHz, 3GB RAM)

Code: Alles auswählen

*und wech*

Vielleicht sollten wir die Lösungen morgen wieder löschen, damit wir niemanden um den Spaß bringen, es selbst heraus zu knobeln?

Gruß.
Mick.

*edit*
hab's gelöscht.

[nemomuk]

Ich habe meine Lösung mal wieder raus...

[pillmuncher]

Das ist meine beste Lösung, ca. 13 msec:

Code: Alles auswählen

def amicable_pairs(n):
    """snip"""

import itertools

flatten = itertools.chain.from_iterable

def test(n):
    return sum(flatten(amicable_pairs(n)))

print test(10000)

Wollte die schon vor 6 Monaten posten, war aber verhindert.
Sonntag lösch ich sie wieder.
[edit]done[/edit]