SPOJ PRIME1 Laufzeitfehler NZEC nur auf der Seite

[hulkhomer]

Hallo!

Ich arbeite an dem Problem und auf meinem Rechner funktioniert es. Auf SPOJ bekomme ich allerdings einen Laufzeitfehler. Kann es daran liegen, dass die Liste mit allen(!) Primzahlen bis zur jeweiligen Obergrenze zu groß wird?

(Was die Geschwindigkeit angeht, habe ich schon hier im Forum gelesen, dass meine Herangehensweise nicht optimal ist.)

Code: Alles auswählen

def sieve(n):
    np1 = n + 1
    s = list(range(np1)) 
    s[1] = 0
    sqrtn = int(round(n**0.5))
    for i in range(2, sqrtn + 1): 
        if s[i]:
            s[i*i: np1: i] = [0] * len(range(i*i, np1, i))
    return s
maximum=0
liste=[]
list_prim=[]
t=input()
for i in range(int(t)):
    mn=input()
    liste.append(mn.split())
#liste mit Einträgen fertig
for i in liste:
    for k in i:
        m_test=int(k)
        if m_test>maximum:
            maximum=m_test
list_prim=sieve(maximum)
for k in range(len(liste)):
    m=int(liste[k][0])
    n=int(liste[k][1])
    for l in list_prim:
        if l>=m and l<=n:
            print(l)
    print()

[Sirius3]

@hulkhomer: das kannst Du doch selbst rechnen. Es können Zahlen bis zu einer Milliarde vorkommen. Würden für jedes Element der Liste nur 4 Bytes benötigt, wären das schon 4GB, also mehr Speicher, als Dir zur Verfügung steht.

Warum hast Du in Zeile 24 eine Schleife über einen Index einer Liste? Du weißt doch wie es richtig geht
Du wandelst die Eingabe an mehr als einer Stelle in Zahlen um; das sollte nur einmal passieren und zwar möglichst gleich nach dem Einlesen.
Um das Maximum einer Liste zu finden, gibt es die max-Funktion.
Was ist der Vorteil np1 zu schreiben, statt n+1, außer, dass man sich den Zweck einer zusätzlichen Variable merken muß?
Variablen sollten immer erst dann initialisiert werden, kurz bevor man sie braucht, also maximum nicht vor Zeile 17 und list_prim nie.

[hulkhomer]

Danke für dein Feedback! Ich werde mich da wohl mal drum kümmern.

Was du über die Menge an Speicher gesagt hast, leuchtet mir ein. Ich habe immer nur mit kleinen Zahlen getestet

Was die notwendigen Primzahlen angeht, werde ich wohl mein Zahlentheoriewissen auffrischen müssen.