NumPy Project Euler Problem 7

This entry is part 7 of 9 in the series NumPy Project Euler

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.

Series NavigationNumPy Project Euler Problem 6NumPy Project Euler Problem 8
By the author of NumPy Beginner's Guide, NumPy Cookbook and Instant Pygame. If you enjoyed this post, please consider leaving a comment or subscribing to the RSS feed to have future articles delivered to your feed reader.
Share
This entry was posted in programming and tagged , , , . Bookmark the permalink.