Summation von Primzahlen unter einer gegebenen Zahl in Python

Question

Ich habe den folgenden Code-Block geschrieben, um die Summe aller Primzahlen unter einer bestimmten Zahl zu berechnen - 2 000 000, um genau zu sein, jedoch dauert es ziemlich lange ausführen; 20 Sekunden:

def summation_of_primes_below_n(n): 
list = [] 
sum = 0 
for i in range(2, n): 
    if checks_if_prime(i) == True: 
     list.append(i) 
return list 
for j in list: 
    sum = sum + j 
return sum 

def checks_if_prime(n): 
    if n == 2: 
     return True 
    import math 
    for i in range(2, math.ceil(math.sqrt(n))+1): 
     if n%i == 0: 
      return False 
     elif i == math.ceil(math.sqrt(n)): 
      return True 

print(summation_of_primes_below_n(2000000)) 

Also fragte ich mich, ob es einen Weg gab, um meinen Code effizienter zu machen. Ich würde mich sehr über einen entsprechenden Ratschlag freuen. Außerdem würde ich bevorzugen, dass Sie mehr grundlegende Lösungen geben, da ich ein Anfänger bin und die Logik für dasselbe zur Verfügung stelle. Danke vielmals!

Answer 1

Sie können beginnen, indem Sie einen besseren Algorithmus implementieren. Für zB: Sieve of Eratosthenes

Oder wenn Sie mit Ihrem aktuellen Logik zufrieden sind, dann einige Optimierungen, die helfen können:

für ungerade Zahlen

• prüfen nur: nur

  for i in range(3, n, 2):

• prüfen für anzahl von form 6n+1, 6n+5

• Sie brauchen nicht Um dies zu überprüfen: elif i == math.ceil(math.sqrt(n)): für jede Iteration. Wenn die Steuerung über die Schleife hinausgegangen ist, dann ist die Nummer prime

• Sie können Ihre check_prime in generator pattern konvertieren. Könnte eine gewisse Redundanz einsparen und möglicherweise die Fundstelle verbessern.