Anzahl der Möglichkeiten eine Zahl als Summe von Primzahlen darzustellen
Verfasst: Mittwoch 17. März 2021, 11:59
Hi, wie ihr im Betreff schon gelesen habt, geht es um ein mathematisches Problem,
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?
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())