# Tag Info

37

That's not the sieve of Eratosthenes It's rather prime trial division. Your filter for 2 lets 1/2 of all numbers through, your filter for 3 lets 2/3 of all remaining numbers through, etc. So 1/2 * 2/3 * 4/5 * 6/7 = 22% of all numbers make it through your filters for 2, 3, 5 and 7, so your filter for 11 will have to check 22% of all numbers. The real sieve of ...

12

Back to the roots - be lazier! (Taking this in another direction than my first answer, and it's different/long enough that I don't want to mix them.) We can vastly improve your approach by not eagerly adding filters and instead only adding filters up to the square root of the current candidate number. And I found an in my opinion neat way to do that. ...

8

Bonus points for coming up with something that is both "interesting" and "technically correct"; but that's about where it stops. It's certainly not fast. Think about what's happening here: for every single call of eval or asmod, you're chaining another layer of filter - with a new function - on your generator. That simply won't scale. You'...

5

Built-in functions As mentioned by Marc, Since Python 3.8 you can use math.isqrt. This is faster. It is also guaranteed to be accurate when the size of the argument exceeds the number of bits of mantissa in a float. Type coercion sieve_arr = array('i', [True for _ in range(n+1)]) Your array is declared to hold 'i' values: integers. But you are trying to ...

3

Your sieve can be optimized further. Pull the case for i = 2 outside of the for loop and then change the for loop to only check odd indexes. Also use slice assignment instead of a nested loop. This code is 10x faster (<100ms to sieve primes to 1M compared to >1s for your sieve). def sieve2a(n=80): """Sieve of Erathosthenes"&...

2

Agreed, this is not the Sieve of Eratosthenes. This is trial division by primes. (As long as you're doing trial division, you can do it slightly better, and only test up to the square root of the number.) Replace the while loop, making it clearer and more pythonic: for test in num_list: It is inefficient to delete from the middle of a list in python, which ...

1

Unused variables op_count is declared in the global scope, pulled into the primes_goto local scope, but is never used. It may be deleted. Unnecessary Globals limitN and pr_count are declared in the global scope, but only ever used inside the primes_goto function. They may be removed from the global scope, and simply declared inside the primes_goto function....

1

You can use bitarray, this tends to be a little faster. The code using bitarray is from bitarray import bitarray import time from math import sqrt, ceil, log def primes_goto2(index: int): prime_up_to = ceil(index * (log(index) + log(log(index)))) + 4 primes = bitarray(prime_up_to) primes.setall(True) primes[0] = primes[1] = False primes[...

1

You can make this part a bit faster: for j in range(i*3, limitN, i*2): not_prime.add(j) Better start at i*i, and better don't do your own loop. So it becomes: not_prime.update(range(i*i, limitN, i*2))

Only top voted, non community-wiki answers of a minimum length are eligible