NumPy Project Euler Problem 7

Project Euler Problem 7 is about prime numbers. So I implemented a Sieve of Eratosthenes with NumPy. I am not following the algorithm to the letter, but I believe that the result is the same.

1. Create a list of consecutive integers

The first mandatory step is to create a list of natural numbers. NumPy has the arange function for that.

1
a = numpy.arange(i, i LIM, 2)

2. Sieve out multiples of p

Not sure whether this is what Eratosthenes wanted us to do, but it works. Below we are passing a NumPy array and getting rid of all the elements that have a 0 remainder, when divided by p.

1
a = a[a % p != 0]

Below is the entire code for this problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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]

If you liked this post and are interested in NumPy check out NumPy Beginner's Guide by yours truly.