Sieve of Eratosthenes – Finding Primes Python

by

You’re not quite implementing the correct algorithm:

In your first example, primes_sieve doesn’t maintain a list of primality flags to strike/unset (as in the algorithm), but instead resizes a list of integers continuously, which is very expensive: removing an item from a list requires shifting all subsequent items down by one.

In the second example, primes_sieve1 maintains a dictionary of primality flags, which is a step in the right direction, but it iterates over the dictionary in undefined order, and redundantly strikes out factors of factors (instead of only factors of primes, as in the algorithm). You could fix this by sorting the keys, and skipping non-primes (which already makes it an order of magnitude faster), but it’s still much more efficient to just use a list directly.

The correct algorithm (with a list instead of a dictionary) looks something like:

def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

(Note that this also includes the algorithmic optimization of starting the non-prime marking at the prime’s square (i*i) instead of its double.)

More Related Contents:

  1. Fastest way to list all primes below N
  2. Adding wheel factorization to an indefinite sieve
  3. code that check if number is prime number [duplicate]
  4. How to implement an efficient infinite generator of prime numbers in Python?
  5. Check if a number is a perfect square
  6. Is there a math nCr function in python? [duplicate]
  7. How can I check if two segments intersect?
  8. isPrime Function for Python Language
  9. Print series of prime numbers in python
  10. Round float to x decimals?
  11. Python and Powers Math
  12. Math operations from string [duplicate]
  13. Difference between the built-in pow() and math.pow() for floats, in Python?
  14. Python: sort function breaks in the presence of nan
  15. How can I quickly estimate the distance between two (latitude, longitude) points?
  16. How to get all combination of n binary value? [duplicate]
  17. Linear regression of arrays containing NANs in Python/Numpy
  18. how can i show an irrational number to 100 decimal places in python?
  19. Is cube root integer?
  20. Multiple variables in SciPy’s optimize.minimize
  21. Rotate point about another point in degrees python
  22. Python floating-point math is wrong [duplicate]
  23. Computing Standard Deviation in a stream
  24. How to pad a string with leading zeros in Python 3 [duplicate]
  25. Sieve of Eratosthenes – Primes between X and N
  26. How to perform bilinear interpolation in Python
  27. Getting the subsets of a set in Python
  28. Python cos(90) and cos(270) not 0
  29. counting combinations and permutations efficiently
  30. How do I get a decimal value when using the division operator in Python?

Leave a Comment