ich versuche mich derzeit an einem Problem der Seite https://projecteuler.net und zwar geht es darum, die kleinste Zahl zu finden, die auf über 5000 Möglichkeiten als Summe von Primzahlen darstellbar ist. Dazu habe ich ein Programm geschrieben, das theoretisch diese gesuchte Zahl findet. Leider stürzt es immer aufgrund eines MemoryErrors ab. Könnte da jemand mal drüberschauen und Tipps geben, wie man dieses Programm effizienter gestalten könnte?
Code: Alles auswählen
from itertools import combinations_with_replacement
def isPrime (zahl):
if zahl < 2:
return False
elif zahl == 2:
return True
else:
for i in range(2,int(zahl/2)+1):
if (zahl % i) == 0:
return False
return True
def primesTil(zahl):
liste = []
for k in range(zahl+1):
if isPrime(k):
liste.append(k)
return liste
def sums(zahl, kombinationen):
liste = []
liste2 = list(combinations_with_replacement(primesTil(zahl),kombinationen))
for m in liste2:
ergebnis = 0
for n in m:
ergebnis += n
if ergebnis == zahl:
liste.append(ergebnis)
return liste
def anzahl(zahl):
ergebnis = 0
for o in range(int(zahl/2)+1):
ergebnis += len(sums(zahl,o))
return ergebnis
def anzahlGesucht():
zahl = 30
while True:
print(str(zahl) +": "+ str(anzahl(zahl)))
if anzahl(zahl) > 5000:
break
zahl += 1
return zahl
print(anzahlGesucht())
