This is my code in python for calculation of sum of prime numbers less than a given number.
What more can I do to optimize it?
import math
primes = [2,] #primes store the prime numbers
for i in xrange(3,20000,2): #i is the test number
x = math.sqrt(i)
isprime = True
for j in primes: #j is the devider. only primes are used as deviders
if j <= x:
if i%j == 0:
isprime = False
break
if isprime:
primes.append(i,)
print sum (primes,)
You can use a different algorithm called the Sieve of Eratosthenes which will be faster but take more memory. Keep an array of flags, signifying whether each number is a prime or not, and for each new prime set it to zero for all multiples of that prime.
N = 10000
# initialize an array of flags
is_prime = [1 for num in xrange(N)]
is_prime[0] = 0 # this is because indexing starts at zero
is_prime[1] = 0 # one is not a prime, but don't mark all of its multiples!
def set_prime(num):
"num is a prime; set all of its multiples in is_prime to zero"
for x in xrange(num*2, N, num):
is_prime[x] = 0
# iterate over all integers up to N and update the is_prime array accordingly
for num in xrange(N):
if is_prime[num] == 1:
set_prime(num)
primes = [num for num in xrange(N) if is_prime[num]]
You can actually do this for pretty large N if you use an efficient bit array, such as in this example (scroll down on the page and you'll find a Sieve of Eratosthenes example).
Another thing you could optimize is move the sqrt computation outside the inner loop. After all, i stays constant through it, so there's no need to recompute sqrt(i) every time.
primes = primes + (i,) is very expensive. It copies every element on every pass of the loop, converting your elegant dynamic programming solution into an O(N2) algorithm. Use lists instead:
primes = [2]
...
primes.append(i)
Also, exit the loop early after passing sqrt(i). And, since you are guaranteed to pass sqrt(i) before running off the end of the list of primes, update the list in-place rather than storing isprime for later consumption:
...
if j > math.sqrt(i):
primes.append(i)
break
if i%j == 0:
break
...
Finally, though this has nothing to do with performance, it is more Pythonic to use range instead of while:
for i in range(3, 10000, 2):
...
Just another code without using any imports:
#This will check n, if it is prime, it will return n, if not, it will return 0
def get_primes(n):
if n < 2:
return 0
i = 2
while True:
if i * i > n:
return n
if n % i == 0:
return 0
i += 1
#this will sum up every prime number up to n
def sum_primes(n):
if n < 2:
return 0
i, s = 2, 0
while i < n:
s += get_primes(i)
i += 1
return s
n = 1000000
print sum_primes(n)
EDIT: removed some silliness while under influence
All brute-force type algorithms for finding prime numbers, no matter how efficient, will become drastically expensive as the upper bound increases. A heuristic approach to testing for primeness can actually save a lot of computation. Established divisibility rules can eliminate most non-primes "at-a-glance".
