Jump to content
  • Advertisement
Sign in to follow this  
Storyyeller

sieve of eratosthenes function count optimization

This topic is 2661 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I implemented the sieve of eratosthenes in Python, and now I am attempting to make it faster. However, I am really confused. In the second version, I changed it to only test odd numbers and not test division by 2, but the function count is exactly the same. How can this be?

Here is the original version

def getprimelist(n):
primes = []
candidates = range(2, n)
stop = int(n ** .5)

while(candidates[0] <= stop):
p = candidates[0]
primes.append(p)

f = lambda x: x%p > 0
candidates = filter(f, candidates)
return primes + candidates


937573 function calls in 4.908 CPU seconds

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)
65 0.000 0.000 0.000 0.000 :0(append)
65 2.502 0.038 4.766 0.073 :0(filter)
1 0.003 0.003 0.003 0.003 :0(range)
1 0.116 0.116 0.116 0.116 :0(setprofile)
1 0.001 0.001 4.792 4.792 <string>:1(<module>)
1 0.000 0.000 4.908 4.908 profile:0(gpl(99999))
0 0.000 0.000 profile:0(profiler)
937438 2.264 0.000 2.264 0.000 sieve.py:13(<lambda>)
1 0.022 0.022 4.791 4.791 sieve.py:4(getprimelist)

Here is the altered version

def getprimelist(n):
primes = [2]
candidates = xrange(3, n, 2)
stop = int(n ** .5)

while(candidates[0] <= stop):
p = candidates[0]
primes.append(p)

f = lambda x: x%p > 0
candidates = filter(f, candidates)
return primes + candidates


937573 function calls in 4.858 CPU seconds

Ordered by: standard name

ncalls tottime percall cumtime percall filename:lineno(function)
65 0.000 0.000 0.000 0.000 :0(append)
65 2.577 0.040 4.829 0.074 :0(filter)
1 0.004 0.004 0.004 0.004 :0(range)
1 0.000 0.000 0.000 0.000 :0(setprofile)
1 0.000 0.000 4.858 4.858 <string>:1(<module>)
1 0.000 0.000 4.858 4.858 profile:0(gpl(99999))
0 0.000 0.000 profile:0(profiler)
937438 2.252 0.000 2.252 0.000 sieve.py:13(<lambda>)
1 0.024 0.024 4.857 4.857 sieve.py:4(getprimelist)

Share this post


Link to post
Share on other sites
Advertisement
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!