Finding Prime Numbers - Part 1

Writing a program to search for prime numbers seems like a simple task. Doing it quickly is more challenging. Let's start the simple way in Python:

def is_prime(n):
    "Returns whether n is prime or not"
    for i in range(2, n):
        if n%i==0: return False
    return True # No factors found

for i in range(2, 100):
    if is_prime(i): print i, "is prime"

It works:

2 is prime
3 is prime
5 is prime
7 is prime
11 is prime
...

However, use it to find all the prime numbers up to 1,000,000 and you might be waiting a while. There is one obvious optimization. Factors always come in pairs. For example, factor pairs of 100 are (1,100), (2,50), (4,25), (5,20), (10,10). Note that each factor pair has one factor less than or equal to the square root, and one greater. This means that our code only has to search up to the square root of the number.

import math
def is_prime(n):
    "Returns whether n is prime or not"
    for i in range(2, math.sqrt(n)):
        if n%i==0: return False
    return True # No factors found

Now, let's compare this to the original algorithm. We'll use the time it takes to find all the prime numbers up to 20,000 for the comparison.

is_prime_1:
7.64995503426 seconds
is_prime_2:
0.169955968857 seconds

(All times are measured on a Athlon XP 2000+ with Ubuntu 7.04 (kernel 2.6.20) and Python 2.5.1)

It's now much, much, faster. However, we're not done yet. In the next part of this three part series, we will explore a more efficient algorithm that will make searching for prime numbers much faster.

You can download the code from this tutorial below:

primes.py