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.
The first mandatory step is to create a list of natural numbers.
NumPy has the arange
function for that:
a = numpy.arange(i, i + LIM, 2)
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]