optymalizacja kodu

0

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)
0

Najbardziej trywialne optymalizacje:

  • nie sprawdzaj liczb parzystych, bo tylko 2 jest parzyste i jest liczbą pierwszą!
  • sprawdzaj liczby tylko do sufitu z sqrt(n) a nie z jakiegoś n/2
0

Powinieneś użyć innego sposobu wyszukiwania liczb pierwszych, np. sito Eratostenesa.

0

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 ;)

0

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

0
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

0

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 ;)

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0