mam za zadanie znalezc sume wszystkich liczb pierwszych ponizej 2 milionow, kod niby dziala ale wykonuje sie strasznie dlugo, jak go mozna zoptymalizowac?
import time
t = time.clock()
def pierwsza(arg):
for j in range(2,int(arg/2)):
if arg%j==0:
return 0
return 1
sum = 2
for i in range(3,2000000,2):
if pierwsza(i)==1:
sum = sum + i
print(sum)
print(time.clock()-t)
Najbardziej trywialne optymalizacje:
Powinieneś użyć innego sposobu wyszukiwania liczb pierwszych, np. sito Eratostenesa.
Proponuję zrobic Sito Eratostenesa a potem zsumować pozostałe liczby, zamiast tak szukać w obiegu pętli każdą po kolei ;)
Masz tu złożoność n^2, więc dość duża, zwłaszcza przy tylu rekordach ;)
Znalazłem gdzieś takie ultra krótkie sito :D
from datetime import datetime
d1=datetime.now()
def eratosthenes():
'''Yields the sequence of prime numbers via the Sieve of Eratosthenes.'''
D = {} # map composite integers to primes witnessing their compositeness
q = 2 # first integer to test for primality
while 1:
if q not in D:
yield q # not marked composite, must be prime
D[q*q] = [q] # first multiple of q not already marked
else:
for p in D[q]: # move each witness to its next multiple
D.setdefault(p+q,[]).append(p)
del D[q] # no longer need D[q], free memory
q += 1
suma=0
for i in eratosthenes():
if i>2000000:
break
suma+=i
print(suma)
print (datetime.now()-d1)
Mi wychodzi 142913828922 w czasie 0:00:02.194908
Spine napisał(a)
Znalazłem gdzieś takie ultra krótkie sito :D
Ani to krótkie, ani wydajne, przynajmniej w tym wypadku można to znacznie uprościć:
http://ideone.com/t1q5p - banalna implementacja, czas: 1.47s
http://ideone.com/vufWn - podana w poście wyżej, czas: 4.66s
Niezłe :) Na moim i5 wykonuje się to w czasie 0:00:00.674815 ;) Dzięki. To wcześniejsze sito co dałem, to gdzieś na dysku miałem ściągnięte, Twoje rzeczywiście dużo lepsze ;)