Eratosthenes sieve

The most efficient static sieve generator in python I have seen so far.
Returns the list of primes, that are not greater than n.

python

def eras(n):
  siv=range(n+1)
  siv[1]=0
  sqn=int(round(n**0.5))
  for i in range(2,sqn+1):
    if siv[i]!=0:
        siv[2*i:n/i*i+1:i]=[0]*(n/i-1)
  return filter(None,siv)

Contributors

Replies

Views

9 Years

Discussion Span

3 Years Ago

Last Post by vegaseat

Replace line 7:
siv[2i:n/ii+1:i]=[0](n/i-1)
by
siv[i * i:n/ii+1:i]=[0]*(n/i-i+1)
to make it even faster.

Edited 4 Years Ago by david.raimosson: My answer seems to have been reformatted somehow.

Hmmm, I put it to the test ...

''' primelist_timing7.py
yet another primelist timing for speed
'''

import timeit

def time_function(stmt, setup):
    """use module timeit to time functions"""
    # to enable garbage collection start setup with 'gc.enable();'
    #setup = 'gc.enable();' + setup
    t = timeit.Timer(stmt, setup)
    # doing 10 passes * 100000 gives the time in microseconds/pass
    # (a little less precise but saves time)
    elapsed = (100000 * t.timeit(number=10))
    print("%-18s --> %0.2f microseconds/pass" % (stmt, elapsed))

def eras(n):
    """
    returns  a list of primes 2 to n n
    """    
    siv = range(n+1)
    siv[1] = 0
    sqn = int(round(n**0.5))
    for i in range(2, sqn+1):
        if siv[i] != 0:
            siv[2*i:n/i*i+1:i] = [0]*(n/i-1)
    return filter(None, siv)

def eras2(n):
    """
    returns  a list of primes 2 to n
    """    
    siv = range(n+1)
    siv[1] = 0
    sqn = int(round(n**0.5))
    for i in range(2, sqn+1):
        if siv[i] != 0:
            #siv[2*i:n/i*i+1:i] = [0]*(n/i-1)
            siv[i*i:n/i*i+1:i] = [0]*(n/i-i+1) 
    return filter(None, siv)

def eras_dns(n):
    """
    returns  a list of primes 2 to < n
    """
    sieve = [True] * (n>>1)
    for x in range(3, int(n**0.5)+1, 2):
        if sieve[x>>1]:
            sieve[(x*x)>>1::x] = [False] * ((n-x*x-1)//(x<<1)+1)
    return [2] + [(x<<1)+1 for x in range(1, n>>1) if sieve[x]]

# time the function
stmt = 'eras(1000000)'
setup = 'from __main__ import eras'
time_function(stmt, setup)

# time the function
stmt = 'eras2(1000000)'
setup = 'from __main__ import eras2'
time_function(stmt, setup)

# time the function
stmt = 'eras_dns(1000000)'
setup = 'from __main__ import eras_dns'
time_function(stmt, setup)

# extra test
print(eras(61))
print(eras2(61))
print(eras_dns(61))

''' result with Python 2.7.3 ...
eras(1000000)      --> 276458.51 microseconds/pass
eras2(1000000)     --> 290727.66 microseconds/pass
eras_dns(1000000)  --> 218466.05 microseconds/pass
'''

Actually, the fastest algorithm uses the Python module numpy ...

''' primelist_timing7a.py
yet another prime list timing for speed
using module numpy gives the fastest algorithm
tested with Python27
'''

import timeit
import numpy as np

def time_function(stmt, setup):
    """use module timeit to time functions"""
    # to enable garbage collection start setup with 'gc.enable();'
    #setup = 'gc.enable();' + setup
    t = timeit.Timer(stmt, setup)
    # doing 10 passes * 100000 gives the time in microseconds/pass
    # (a little less precise but saves time)
    elapsed = (100000 * t.timeit(number=10))
    print("%-18s --> %0.2f microseconds/pass" % (stmt, elapsed))

def eras(n):
    """
    returns  a list of primes 2 to n n
    """    
    siv = range(n+1)  # for Python3 use siv = list(range(n+1))
    siv[1] = 0
    sqn = int(round(n**0.5))
    for i in range(2, sqn+1):
        if siv[i] != 0:
            siv[2*i:n/i*i+1:i] = [0]*(n/i-1)
    return filter(None, siv)

def eras2(n):
    """
    returns  a list of primes 2 to n
    """    
    siv = range(n+1)  # for Python3 use siv = list(range(n+1))
    siv[1] = 0
    sqn = int(round(n**0.5))
    for i in range(2, sqn+1):
        if siv[i] != 0:
            #siv[2*i:n/i*i+1:i] = [0]*(n/i-1)
            siv[i*i:n/i*i+1:i] = [0]*(n/i-i+1) 
    return filter(None, siv)

def eras_dns(n):
    """
    returns  a list of primes 2 to < n
    """
    sieve = [True] * (n>>1)
    for x in range(3, int(n**0.5)+1, 2):
        if sieve[x>>1]:
            sieve[(x*x)>>1::x] = [False] * ((n-x*x-1)//(x<<1)+1)
    return [2] + [(x<<1)+1 for x in range(1, n>>1) if sieve[x]]

def np_primes1(limit):
    """
    returns a numpy array of primes, 2 <= p < limit
    """
    # create a sieve of ones
    is_prime = np.ones(limit + 1, dtype=np.bool)
    for n in range(2, int(limit**0.5 + 1.5)):
        if is_prime[n]:
            is_prime[n*n::n] = 0
    return np.nonzero(is_prime)[0][2:]

# time the function
stmt = 'eras(1000000)'
setup = 'from __main__ import eras'
time_function(stmt, setup)

# time the function
stmt = 'eras2(1000000)'
setup = 'from __main__ import eras2'
time_function(stmt, setup)

# time the function
stmt = 'eras_dns(1000000)'
setup = 'from __main__ import eras_dns'
time_function(stmt, setup)

# time the function
stmt = 'np_primes1(1000000)'
setup = 'from __main__ import np_primes1'
time_function(stmt, setup)

# extra test ...
print('-'*70)
print(eras(61))
print(eras2(61))
print(eras_dns(61+1))
print(list(np_primes1(61+1)))

''' result with Python 2.7.5 ...
eras(1000000)      --> 140160.01 microseconds/pass
eras2(1000000)     --> 160555.08 microseconds/pass
eras_dns(1000000)  --> 120546.30 microseconds/pass
np_primes1(1000000) --> 12757.87 microseconds/pass
----------------------------------------------------------------------
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61]
'''

python