python - Sieve of Eratosthenes - Primes between X and N -

python - Sieve of Eratosthenes - Primes between X and N -

i found highly optimised implementation of sieve of eratosthenes python on code review. have rough thought of it's doing must admit details of it's workings elude me.

i still utilize little project (i'm aware there libraries utilize function).

here's original:

''' sieve of eratosthenes implementation gareth rees http://codereview.stackexchange.com/questions/42420/sieve-of-eratosthenes-python ''' def sieve(n): """return array of primes below n.""" prime = numpy.ones(n//3 + (n%6==2), dtype=numpy.bool) in range(3, int(n**.5) + 1, 3): if prime[i // 3]: p = (i + 1) | 1 prime[ p*p//3 ::2*p] = false prime[p*(p-2*(i&1)+4)//3::2*p] = false result = (3 * prime.nonzero()[0] + 1) | 1 result[0] = 3 homecoming numpy.r_[2,result]

what i'm trying accomplish modify homecoming primes below n starting at x that:

primes = sieve(50, 100)

would homecoming primes between 50 , 100. seemed easy enough, tried replacing these 2 lines:

def sieve(x, n): ... in range(x, int(n**.5) + 1, 3): ...

but reason can't explain, value of x in above has no influence on numpy array returned!

how can modify sieve() only homecoming primes between x , n

the implementation you've borrowed able start @ 3 because replaces sieving out multiples of 2 skipping numbers; that's 2*… appear multiple times in code about. fact 3 next prime hardcoded in on place, let's ignore moment, because if can't past special-casing of 2, special-casing of 3 doesn't matter.

skipping numbers special case of "wheel". can skip sieving multiples of 2 incrementing 2; can skip sieving multiples of 2 , 3 alternately incrementing 2 , 4; can skip sieving multiples of 2, 3, 5, , 7 alternately incrementing 2, 4, 2, 4, 6, 2, 6, … (there's 48 numbers in sequence), , on. so, could extend code first finding primes x, building wheel, using wheel find primes between x , n.

but that's adding lot of complexity. , 1 time far beyond 7, cost (both in time, , in space storing wheel) swamps savings. , if whole goal not find primes before x, finding primes before x don't have find them seems kind of silly. :)

the simpler thing find primes n, , throw out ones below x. can trivial alter @ end:

primes = numpy.r_[2,result] homecoming primes[primes>=x]

or course of study there ways without wasting storage initial primes you're going throw away. they'd bit complicated work algorithm (you'd want build array in sections, drop each section that's exclusively < x go, stack remaining sections); far easier utilize different implementation of algorithm isn't designed speed , simplicity on space…

and of course of study there different prime-finding algorithms don't require enumerating primes x in first place. if want utilize implementation of algorithm, doesn't matter.

python algorithm numpy primes