xrange für long integers

[raorao]

Hoi mitenand!

Ich beschäftige mich mit der Lösung des Projekts Euler 12...
Es soll die erste Triangle Number (= 1+2+3+4+...) welche über 500 Teiler hat bestimmt werden. Um die Anzahl Teiler zu bestimmen benutze ich folgende Funktion:

Code: Alles auswählen

def f1(zahl):
    t = [x for x in xrange(1, zahl/2 + 1) if zahl % x == 0]
    return len(t) + 1

Für sehr grosse Zahlen wird aber natürlich ein OverflowError geworfen, da xrange "int" erwartet... Daher folgende Funktion um dies zu umgehen:

Code: Alles auswählen

def f2(zahl):
    t = []
    a = 1
    while a < zahl/2 + 1:
        if zahl % a == 0:
            t.append(1)
        a += 1
    return len(t) + 1

Diese Variante braucht aber mindestens doppelt soviel Rechenzeit für dieselbe Zahl und ist deshalb für obige Aufgabe auch nicht geeignet... Gibt es eine Möglichkeit, trotzdem longints an xrange zu übergeben oder aber habt ihr einen ganz andern viel schnelleren Ansatz, der euch die Anzahl Teiler liefert? Herzlichen Dank für eure Ideen!

Gruss raorao

[Darii]

Speicher die maximale Zahl zwischen.

Code: Alles auswählen

    maximum = zahl/2 + 1
    while a < maximum:

sonst wird das jedes Mal aufs neue Berechnet.

[sma]

Für sehr grosse Zahlen wird aber natürlich ein OverflowError geworfen, da xrange "int" erwartet...

Mach's dir selbst:

Code: Alles auswählen

def myrange(start, end=None, step=1):
    if end is None:
        start, end = 0, start
    while start < end:
        yield start
        start += step

Oder nimm Python 3.1.

Code: Alles auswählen

for i in range(100000000000000000000000000000000000, 100000000000000000000000000000000005):
    print(i)

Stefan

[numerix]

oder aber habt ihr einen ganz andern viel schnelleren Ansatz, der euch die Anzahl Teiler liefert?

1. Gesucht ist hier die ANZAHL der Teiler, nicht die Teiler selbst. Warum also die Teiler aufwändig in einer Liste sammeln. Überflüssig und teuer.

2. Wenn du einen Teiler einer Zahl n gefunden hast, hast du - von einem Sonderfall abgesehen - immer gleich zwei Teiler von n gefunden. Wenn du das zu Ende denkst, merkst du, dass du gar nicht bis n/2 nach Teilern suchen musst, sondern viel früher aufhören kannst.

Wenn du die beiden Aspekte umsetzt, kommst du mit der brute-force-Methode in wenigen Sekunden zur Lösung. (Das range()-Problem entfällt dann von ganz allein.)

[raorao]

Die ersten beiden Antworten haben zwar die Berechnungszeit wesentlich verkürzt, bzw. möglicher gemacht, der entscheidende Hinweis von Numerix hat dann aber zu folgendem Code geführt, der nochmals Welten schneller ist (da weitaus effizienterer Ansatz):

Code: Alles auswählen

import time
import math

def anzTeiler(zahl):
    c = 0
    for x in xrange(1, int(math.sqrt(zahl) + 1)):
        if zahl % x == 0:
            c += 2
    return c

def berechnen(minimum):
    z = 1
    tz = 0
    while True:
        tz += z
        anzT = anzTeiler(tz)
        if anzT > minimum:
            break
        z += 1
    return tz


t = time.time()
tz = berechnen(500)
print "Triangelzahl:", tz
print "Berechnungszeit:", time.time()-t

Herzlichen Dank allen, war sehr lehrreich...
Auf ein andermal...