codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
# 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"
Private
[
?
]
Run code
Submit