Ich möchte die Summe aller Primzahlen unter 1 Million drucken, aber mein Code nimmt viel Zeit in Anspruch. Gibt es eine andere Methode, um den Code schneller auszuführen?

b=1
d = 0
#generates a list of numbers.
while b<1000000:
    b=b+1
    x = 0.0
    a = 0
    #generates a list of numbers less than b. 
    while x<b:
        x=x+1
        #this will check for divisors. 
        if (b/x)-int(b/x) == 0.0:
            a=a+1
    if a==2:
        #if it finds a prime it will add it.
        d=d+b
print(d) 
-3
jain 18 Jän. 2019 im 08:50

3 Antworten

Beste Antwort

Versuchen Sie diesen einfachen Code, er ist sehr schneller als Ihrer :)

import math

def isPrime(n):
   if n == 1:
      return False
   if n == 2:
      return True
   if n > 2 and n % 2 ==0:
      return False

   max_divisor = math.floor(math.sqrt(n))
   for d in range(3, 1 + max_divisor,2):
     if n % d ==0:
        return False
   return True

primes = [x for x in range(1,1000000) if isPrime(x) ==True]
print(sum(primes))
2
Ahmed 18 Jän. 2019 im 07:44

Primalitätstest - Wikipedia

Der einfachste Primalitätstest ist die Versuchsteilung: Prüfen Sie bei einer eingegebenen Zahl n, ob eine Primzahl m von 2 bis √n n gleichmäßig teilt

Ich würde damit beginnen, eine Funktion zu definieren, die einfach prüft, ob eine Zahl eine Primzahl ist oder nicht. Verwenden Sie diese Funktion dann in einer Schleife, die von 3, 5, 7, 9, ..., 999,999 zählt, und prüfen Sie, ob jede Zahl eine Primzahl ist. Wenn sie übereinstimmt, fügen Sie sie einer Summenvariablen hinzu.

from math import sqrt

def is_prime(num):
    # According to trial division we only need to check from 2 -> sqrt(num)
    for x in range(2, int(sqrt(num) + 1)):
        if num % x == 0:
             return False
    return True

sum = 2 # Start with 2 in sum because we skip it to make life easier
for x in range(3, 1000000, 2): # Don't bother checking even numbers
    if is_prime(x):
        sum += x
print("Sum: " + str(sum))

Auf meinem Computer dauert es ungefähr 10 Sekunden, um eine Antwort zu finden, die viel besser ist als Ihre Implementierung.

1
Alexander Freyr 18 Jän. 2019 im 07:28

Eratosthenes-Sieb ist ein sehr grundlegender und recht schneller Primalitätstest-Algorithmus.

Die folgende Implementierung dauert auf einer modernen Maschine ungefähr 400 ms, könnte aber wahrscheinlich weiter optimiert werden.

limit = 1000000
is_prime = [x % 2 for x in range(limit)]
is_prime[1] = False
is_prime[2] = True
for candidate in range(3, limit, 2):
    if is_prime[candidate]:
        for product in range(candidate * 3, limit, candidate * 2):
            is_prime[product] = False
print(sum(x for x in range(limit) if is_prime[x]))
1
Tugrul Ates 18 Jän. 2019 im 08:08