[ create a new paste ] login | about

Link: http://codepad.org/iq6Eotrn    [ raw code | output | fork ]

programmingpraxis - Python, pasted on Jan 16:
# sum of primes less than n
# algorithm of RodionGork
#   for x = 3, 5, 7, 9, ... (odds) up to N
#       for each prime p among those already found up to sqrt(N)
#           check if x is divisible by p
#       if x is not divisible by any of them, add it to already found primes

from time import time

def sumPrimes(n):
    ps, s = [2], 2
    for x in xrange(3, n, 2):
        for p in ps:
            if x % p == 0: break
            if p * p > x:
                s += x
                ps.append(x)
                break
    return s

start = time()
print sumPrimes(350000)
print int(round(1000 * (time() - start))), "milliseconds"


Output:
1
2
5002513514
1335 milliseconds


Create a new paste based on this one


Comments: