3 vote(s)

Add comment

Number of comments: 13

Oops! The second reason I gave is not correct, Wensheng Wang, 2005/02/07
If the reviewer see this, please delete that second reason. Also please indent Alex Martelli's code. thanks.
Add comment

another reason , Kazuo Moriwaka, 2005/02/07
Thanks for making progress. I think another reason why your code is faster is old (my) recipe was create lists each steps, but your code just rewrite numbers to 0.
Add comment

Improvement, Pierre Quentel, 2005/02/13
Very nice recipe, thanks. A slight improvement : the function raises exceptions for some odd numbers (primes(13) for instance). It is safer if you change the value of "half" to len(s)
Add comment

Nice speed, but the indexing is a little opaque..., Michael Spencer, 2005/02/17
Here's the same algorithm with simpler indexing:

def primes2(n): 
    if nHere's the same algorithm with simpler indexing:

def primes2(n): 
    if n

Add comment

How do you add code in the comments, Michael Spencer, 2005/02/17
I've tried surrounding it in pre tags. I give up...
Add comment

Out by 1?, Jimmy Hoeks, 2005/04/22
You say the function returns primes that are less than the argument. Did you mean less than or equal to the argument?

In fact, as it stands, the function can return a prime higher than the argument (try it for 3000, for instance). Changing 's=range(3,n+2,2)' to 's=range(3,n+1,2)' would ensure you get all primes up to and including the argument.
Add comment

Seems to be a bug, Paul Miller, 2005/04/24
For some reason, I get an IndexError for certain prime or prime-power values of n. For example, try n=25, n=251.
Add comment

purpose for better implementation, Giuliano Castelli, 2005/06/07
Would it be possible to implement an analogous so efficient algorithm as primes(n), but with two inputs, primes(s,n), where s is the starting number from which the primes begin to be calculate? Instead of beginning always from 2. Thank you!
Add comment

bug fix, Simon Gomizelj, 2005/10/11
as many of you coders have noticed that with this code there are some values that fail, such as 13, 25, 251, and 3000. there is a simple solution to this problem, the line reads half = (n+1) / 2 should read half = (n+1) / 2 - 1 this variable seems to be the size of the list considering it should be 1/2 of the original list's size because we are working only with odd numbers. however, the coder forgot to take into account that he skipped the odd value of 1 and started straight at three. so half really was the size of the list + 1. most numbers, when looping, had increments that we greater than this + 1, but sometime it fell in it, hence giving an element doesnt exist error.
Add comment

thank all, Wensheng Wang, 2006/06/23
Thank all the commentors and your suggestions. I have made the correction: s=range(3,n+1,2) and half=(n+1)/2-1 Thanks.
Add comment

More pythonesque, Hugh Brown, 2007/08/17
This works the same but has a cleaner loop:

	for i in range(0, int(mroot/2)) :
		m=2*i+3
		if s[i]:
			for j in range((m*m-3)/2, half, m) :
				s[j]=0

Add comment

More pythonesque, Hugh Brown, 2007/08/17
This works the same but has a cleaner loop:

	for i in range(0, int(mroot/2)) :
		m=2*i+3
		if s[i]:
			for j in range((m*m-3)/2, half, m) :
				s[j]=0

Add comment

Twice as fast?, Dr. Drang, 2007/11/06
In my benchmarks (on an Intel iMac with n=1,000,000, n=10,000,000, and n=20,000,000), the recipe code is only about 10% faster than the "Alex" code, although its memory use is probably much smaller.

The code below runs about 50% faster than the "Alex" code and isn't too obscure, I think:

nroot = int(sqrt(n))
sieve = range(n+1)
sieve[1] = 0

for i in xrange(2, nroot+1):
    if sieve[i] != 0:
        m = n/i - i
        sieve[i*i: n+1:i] = [0] * (m+1)

sieve = [x for x in sieve if x !=0]

The slice assignment seems to be the big time saver. The three terms that define the slice are the same as the three terms that define the range for j in the "Alex" code, which is why I think the code is still readable. m is a little tricky; it's the number of multiples of i that are greater than i**2 and less than or equal to n. The integer division used to calculate m will have to be changed for Python 3.

Since zero is false, I suppose the "!= 0" parts could be omitted from the conditionals, but I think it's easier to read with them in.
Add comment