StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POWhy is this algorithm worse?
primarykey
Id
5426237
data
AcceptedAnswerId
5426429
AnswerCount
4
ClosedDate
CommentCount
5
CommunityOwnedDate
CreationDate
2011-03-24T22:14:49.533
FavoriteCount
3
LastActivityDate
2011-03-26T00:23:14.820
LastEditDate
2011-03-26T00:23:14.820
LastEditorUserId
594415
OwnerUserId
594415
ParentId
0
PostTypeId
1
Score
4
ViewCount
337
LastEditorDisplayName
text
Body
In <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow">Wikipedia</a> this is one of the given algorithms to generate prime numbers: <pre><code>def eratosthenes_sieve(n): # Create a candidate list within which non-primes will be # marked as None; only candidates below sqrt(n) need be checked. candidates = [i for i in range(n + 1)] fin = int(n ** 0.5) # Loop over the candidates, marking out each multiple. for i in range(2, fin + 1): if not candidates[i]: continue candidates[i + i::i] = [None] * (n // i - 1) # Filter out non-primes and return the list. return [i for i in candidates[2:] if i] </code></pre> I changed the algorithm slightly. <pre><code>def eratosthenes_sieve(n): # Create a candidate list within which non-primes will be # marked as None; only candidates below sqrt(n) need be checked. candidates = [i for i in range(n + 1)] fin = int(n ** 0.5) # Loop over the candidates, marking out each multiple. candidates[4::2] = [None] * (n // 2 - 1) for i in range(3, fin + 1, 2): if not candidates[i]: continue candidates[i + i::i] = [None] * (n // i - 1) # Filter out non-primes and return the list. return [i for i in candidates[2:] if i] </code></pre> I first marked off all the multiples of 2, and then I considered odd numbers only. When I timed both algorithms (tried 40.000.000) the first one was always better (albeit very slightly). I don't understand why. Can somebody please explain? P.S.: When I try 100.000.000, my computer freezes. Why is that? I have Core Duo E8500, 4GB RAM, Windows 7 Pro 64 Bit. Update 1: This is Python 3. Update 2: This is how I timed: <pre><code>start = time.time() a = eratosthenes_sieve(40000000) end = time.time() print(end - start) </code></pre> UPDATE: Upon valuable comments (especially by nightcracker and Winston Ewert) I managed to code what I intended in the first place: <pre><code>def eratosthenes_sieve(n): # Create a candidate list within which non-primes will be # marked as None; only c below sqrt(n) need be checked. c = [i for i in range(3, n + 1, 2)] fin = int(n ** 0.5) // 2 # Loop over the c, marking out each multiple. for i in range(fin): if not c[i]: continue c[c[i] + i::c[i]] = [None] * ((n // c[i]) - (n // (2 * c[i])) - 1) # Filter out non-primes and return the list. return [2] + [i for i in c if i] </code></pre> This algorithm improves the original algorithm (mentioned at the top) by (usually) 50%. (Still, worse than the algorithm mentioned by nightcracker, naturally). A question to Python Masters: Is there a more Pythonic way to express this last code, in a more "functional" way? UPDATE 2: I still couldn't decode the algorithm mentioned by nightcracker. I guess I'm too stupid.
Tags
<python><algorithm><primes>
Title
Why is this algorithm worse?
singulars
PostAcceptedAnswerId
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. USblackened
UserOwnerUserId
1. USblackened
plurals
PostLinksPostIdRelatedPostId
1. PL
 singulars
 LinkTypeLinkTypeId
 LTLinked
2. PL
 singulars
 LinkTypeLinkTypeId
 LTLinked
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
2. PO
 singulars
 PostTypePostTypeId
 PTAnswer
3. PO
 singulars
 PostTypePostTypeId
 PTAnswer
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 POWhy is this algorithm worse?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 POWhy is this algorithm worse?
 UserUserId
 USJ V
 VoteTypeVoteTypeId
 VTFavorite
3. VO
 singulars
 PostPostId
 POWhy is this algorithm worse?
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.