Sieve of Eratosthenes – Primes between X and N

by

The implementation you’ve borrowed is able to start at 3 because it replaces sieving out the multiples of 2 by just skipping all even numbers; that’s what the 2*… that appear multiple times in the code are about. The fact that 3 is the next prime is also hardcoded in all over the place, but let’s ignore that for the moment, because if you can’t get past the special-casing of 2, the special-casing of 3 doesn’t matter.

Skipping even numbers is a special case of a “wheel”. You can skip sieving multiples of 2 by always incrementing by 2; you can skip sieving multiples of 2 and 3 by alternately incrementing by 2 and 4; you can skip sieving multiples of 2, 3, 5, and 7 by alternately incrementing by 2, 4, 2, 4, 6, 2, 6, … (there’s 48 numbers in the sequence), and so on. So, you could extend this code by first finding all the primes up to x, then building a wheel, then using that wheel to find all the primes between x and n.

But that’s adding a lot of complexity. And once you get too far beyond 7, the cost (both in time, and in space for storing the wheel) swamps the savings. And if your whole goal is not to find the primes before x, finding the primes before x so you don’t have to find them seems kind of silly. 🙂

The simpler thing to do is just find all the primes up to n, and throw out the ones below x. Which you can do with a trivial change at the end:

primes = numpy.r_[2,result]
return primes[primes>=x]

Or course there are ways to do this without wasting storage for those initial primes you’re going to throw away. They’d be a bit complicated to work into this algorithm (you’d probably want to build the array in sections, then drop each section that’s entirely < x as you go, then stack all the remaining sections); it would be far easier to use a different implementation of the algorithm that isn’t designed for speed and simplicity over space…

And of course there are different prime-finding algorithms that don’t require enumerating all the primes up to x in the first place. But if you want to use this implementation of this algorithm, that doesn’t matter.

More Related Contents:

  1. Finding index of nearest point in numpy arrays of x and y coordinates
  2. Find elements of array one nearest to elements of array two
  3. How to invert a permutation array in numpy
  4. Compute *rolling* maximum drawdown of pandas Series
  5. NumPy grouping using itertools.groupby performance
  6. What is the Big O Complexity of Reversing the Order of Columns in Pandas DataFrame?
  7. Cost of len() function
  8. Windows Scipy Install: No Lapack/Blas Resources Found
  9. List of lists into numpy array
  10. Print series of prime numbers in python
  11. How to find the groups of consecutive elements in a NumPy array
  12. Efficient Numpy 2D array construction from 1D array
  13. Replacing Pandas or Numpy Nan with a None to use with MysqlDB
  14. Installing Numpy on 64bit Windows 7 with Python 2.7.3 [closed]
  15. Why does pyplot.contour() require Z to be a 2D array?
  16. How do I print the full NumPy array, without truncation?
  17. Use scipy.integrate.quad to integrate complex numbers
  18. numpy.array.__iadd__ and repeated indices [duplicate]
  19. Polar contour plot in matplotlib – best (modern) way to do it?
  20. Custom transformer for sklearn Pipeline that alters both X and y
  21. Find out if/which BLAS library is used by Numpy
  22. Why is a `for` over a Python list faster than over a Numpy array?
  23. Is there a numpy builtin to reject outliers from a list
  24. Python/Numpy MemoryError
  25. How to determine whether a column/variable is numeric or not in Pandas/NumPy?
  26. Why does numpy have a corresponding function for many ndarray methods?
  27. Python OpenCV2 (cv2) wrapper to get image size?
  28. Setting the fmt option in numpy.savetxt
  29. Append 2D array to 3D array, extending third dimension
  30. How to transform numpy.matrix or array to scipy sparse matrix

Leave a Comment