Sieving integers with the Sieve of Erasthothenes

The Sieve of Eratosthenes (http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) is an algorithm that filters out prime numbers. It iteratively identifies multiples of found primes. This sieve is efficient for primes smaller 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 = numpy.arange(i, i + LIM, 2)
  2. Sieve out 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 rid of all the elements that have a zero remainder, when divided by p:

    a = a[a % p != 0]

The following is the entire code for this problem:

import numpy

LIM = 10 ** 6
N = 10 ** 9
P = 10001
primes = []
p = 2

#By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
#What is the 10 001st prime number?

def check_primes(a, p):
    #2. Sieve out multiples of p
    a = a[a % p != 0]

    return a
for i in xrange(3, N, LIM):
    #1. Create a list of consecutive integers
    a = numpy.arange(i, i + LIM, 2)

    while len(primes) < P:
      a = check_primes(a, p)
      primes.append(p)

      p = a[0]

print len(primes), primes[P-1]
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset