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()