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 100000000Up to 100000000 there are 5761455 primes.real  0m1.914suser  0m1.876ssys   0m0.032stime ./primesieve 100000000Sieve size = 32 kilobytesThreads    = 4100%Prime numbers : 5761455Time elapsed  : 0.0568619 secreal  0m0.206suser  0m0.192ssys   0m0.004stime ./sieve-c 1000000000Up to 1000000000 there are 50847534 primes.real  0m21.408suser  0m21.128ssys   0m0.252stime ./primesieve 1000000000Sieve size = 32 kilobytesThreads    = 4100%Prime numbers : 50847534Time elapsed  : 0.582213 secreal  0m0.607suser  0m2.220ssys   0m0.000sWhere 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 doctestimport mathimport sysimport doctestdef 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 sievedoctest.testmod()def _sum(lst):    s = 0    for i in lst:        s += i    return sdef main(argv):    print(Up to  + argv[1] + there are  +str(_sum(sieve(int(argv[1])+1))) +  primes.)    return 0def target(*args):      return main, Noneif __name__ == '__main__':      import sys    main(sys.argv)
R-Python sieve, 36 times slower than World Record
python;performance;primes;sieve of eratosthenes;rpython