Sieve Erosthenes is much slower when called as a function in Python
I have two blocks of code, both of which I wrote to apply the sieve of eratosthenes to sum all primes up to 2,000,000. This first block, which is only raw code, not wrapped in any function, is this:
N = 2000000
is_prime = (N + 1) * [True]
for candidate in range(2, N + 1):
if is_prime[candidate]:
print(candidate)
for witness in range(2 * candidate, N + 1, candidate):
is_prime[witness] = False
The second block of code has split this functionality into a function that checks for validity, and then a for loop that determines the upper bound. It looks like this:
def is_prime(n):
is_prime = (n + 1) * [True]
for candidate in range(2, int(sqrt(n)) + 1):
if is_prime[candidate]:
for witness in range(2 * candidate, n+1, candidate):
is_prime[witness] = False
return is_prime[n]
for candidate in range(2, LIMIT):
if is_prime(candidate):
print(candidate)
However, a block of code, broken into a function that tests primitiveness, is infinitely slower. I can't let my life determine me what the difference is between these blocks of code. What am I doing wrong?
source to share
The second implementation keeps the list is_prime
as local. Each time the function is called, it "restarts" the computation, initializing the list (n + 1) * [True]
.
So, by restarting the job, you basically do N times when you use the second implementation.
Edit: As @Aaron pointed out correctly in the comments, your print () call makes the second version slower.
Problems
To summarize, the following problems arise:
- The implementation using the function restarts its work
- The second implementation is printing. The first one does not work, which is clearly faster.
- As a side note: your list
is_prime
has the same name as your function. This can cause problems, for example, when using recursion.
<strong> Improvements
As a very simple improvement, you can try (rename and) move the list is_prime
into a global variable. Then when is_prime (n) is called with a number not yet in the list, you expand the list (for example some_list += difference * [True]
) and only compute the difference.
source to share