I decided to write a sieving prime-finding programme and make it fast. It works correctly but counting the primes below 10**9 takes 36 times as primesieve downloaded from http://primesieve.org/.
Now I understand that they have a World Record so they better be fast, but we all know that a compiler is much better than a human at making optimization, so I fear I missed a massive optimization in my implementation.
Some timings:
time ./sieve-c 100000000 Up to 100000000 there are 5761455 primes. real 0m1.914s user 0m1.876s sys 0m0.032s time ./primesieve 100000000 Sieve size = 32 kilobytes Threads = 4 100% Prime numbers : 5761455 Time elapsed : 0.0568619 sec real 0m0.206s user 0m0.192s sys 0m0.004s
time ./sieve-c 1000000000 Up to 1000000000 there are 50847534 primes. real 0m21.408s user 0m21.128s sys 0m0.252s time ./primesieve 1000000000 Sieve size = 32 kilobytes Threads = 4 100% Prime numbers : 50847534 Time elapsed : 0.582213 sec real 0m0.607s user 0m2.220s sys 0m0.000s
Where should I go next for better performance (wheel factorization, memoization, segmentation, parallelism)?
Also, my code is not able to calculate 10**10 or more because that would take up too much space and my computer crashes. Maybe I should try segmentation?
Please note that R-Python is a subset of Python, so you can run my programme with a regular Python too (but it will be much slower).
import doctest
import math
import sys
import doctest
def sieve(limit):
"""
Returns the primes below the `limit`
>>> sieve(9)
[False, False, True, True, False, True, False, True, False]
>>> sieve(100000).count(True)
9592
"""
sieve = [True]*limit
sieve[0],sieve[1] = False, False
sqrt_limit = math.sqrt(limit)
for number, prime in enumerate(sieve):
if prime:
for multiple in xrange(number*2, limit, number):
sieve[multiple] = False
if number > sqrt_limit:
break
return sieve
doctest.testmod()
def _sum(lst):
s = 0
for i in lst:
s += i
return s
def main(argv):
print("Up to " + argv[1] +" there are " +str(_sum(sieve(int(argv[1])+1))) + " primes.")
return 0
def target(*args):
return main, None
if __name__ == '__main__':
import sys
main(sys.argv)
