Public Group

# sieve of eratosthenes function count optimization

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

## 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)

1. 1
2. 2
Rutin
17
3. 3
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633735
• Total Posts
3013596
×