O'Reilly logo

NumPy Cookbook - Second Edition by Ivan Idris

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Sieving integers with the Sieve of Eratosthenes

The Sieve of Eratosthenes (see http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) is an algorithm that filters prime numbers. It iteratively identifies multiples of found primes. The multiples are, by definition, not primes and can be eliminated. This sieve is efficient for primes less than 10 million. Let's now try to find the 10001st prime number.

How to do it...

The first mandatory step is to create a list of natural numbers:

  1. Create a list of consecutive integers. NumPy has the arange() function for that:
    a = np.arange(i, i + LIM, 2)
  2. Sieve out the multiples of p.

    We are not sure if this is what Eratosthenes wanted us to do, but it works. In the following code, we are passing a NumPy array and getting ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required