# 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"