Optimizing a prime number generator in Python

Question

I am looking for any suggestions on optimizing my prime number generator. Could you please include the correction and a little comment on why it will be faster in your response.

def primeList ( highestNumber ):
""" This function takes a integer and returns a list of all primes less than or equal to that integer"""

    numbers = range( 2, highestNumber + 1 ) # creates an inclusive list of all numbers between 2 and highestNumber
    isPrime = [ True ] * len( numbers ) # each element corresponds to an element in numbers and keeps track of whether or not it is prime
    primes = [] # Where I'll build a list of prime numbers

    for i in range( len( numbers )  ):
        if ( isPrime[i] == True ):
            increment = numbers[i]
            position = i + increment
            primes.append( numbers[ i ] )

            while ( position < len( numbers )): # will only execute if the above if statement is true because position will still be greater than len( number )
                isPrime[position] = False  # Sets an element of isPrime to False if it is a multiple of a lower number
                position += increment   
    return primes

Thanks for the info @jrd1. For anyone else interested I found this article on using a [decorator](http://simeonfranklin.com/blog/2012/jul/1/python-decorators-in-12-steps/) in Python — SharkAttacks, Aug 18 '14 at 01:05
I think this question is better suited for [Code Review Stack Exchange](http://codereview.stackexchange.com/) — Barranka, Aug 18 '14 at 02:00
An optimization: All prime numbers except 2 and 3 are either n*6+1 or n*6-1 (e.g. 7=1*6+1; 11=2*6-1). This is provable. Also: Use a generator (e.g. see https://wiki.python.org/moin/Generators), this way you only generate what is consumed, don't need a "highest number", and won't keep the entire list in memory. — AMADANON Inc., Jan 08 '15 at 03:12

score 2 · Answer 1 · edited May 23 '17 at 12:14

2

There's already a great discussion on various prime number generators here: Fastest way to list all primes below N

At that link is a Python script that you can use to compare your algorithm against several others.

edited May 23 '17 at 12:14

Community

1
1

answered Aug 18 '14 at 01:20

Sean Azlin

886
7
21

score 1 · Answer 2 · answered Aug 18 '14 at 01:29

1

You can remove the even numbers greater than 2 from your "numbers" list because surely those even numbers are not prime so you don't have to check them. You can do this by setting the step parameter of the range function.

answered Aug 18 '14 at 01:29

eman.lodovice

192
1
6

Will Ness · Answer 3 · 2014-08-18T23:09:33.360

def primeList ( highestNumber ):
    """ This function takes a integer and returns a list of """
    """ all primes less than or equal to that integer"""

    numbers = range( 3, highestNumber + 1, 2 ) 
    isPrime = [ True ] * len( numbers ) 
    primes = [2] if highestNumber >= 2 else []

    for number in numbers:
        if ( isPrime[(number-3)/2] ):
            increment = number
            position = (number * number - 3) / 2

            if ( position >= len( numbers )):
                primes += (x for x in numbers[(number-3)/2:] 
                             if isPrime[(x-3)/2])
                # primes += (2*i+3 for i in xrange((number-3)/2,
                #                   len(numbers)) if isPrime[i])
                break
            else:
                primes.append( number )
                while ( position < len( numbers )): 
                    isPrime[position] = False  
                    position += increment   
    return primes

Working on odds only is faster and takes less space.

We can start eliminating the multiples of n from n*n because for any n*k, k < n, we have n*k = k*n i.e. it will be eliminated as a multiple of k.

We can stop as soon as the square is above the top - all the multiples will have already been marked in the isPrime list, at this point.

score 0 · Answer 4 · answered Aug 18 '14 at 23:26

The simplest method of computing the primes uses a sieve; it was invented by the Greek mathematician Eratosthenes over two thousand years ago:

def primes(n):
    sieve = [True] * (n+1)
    ps = []
    for p in range(2,n):
        if sieve[p]:
            for i in range(p*p, n, p):
                sieve[i] = False
            ps.append(p)
    return ps

There are faster ways to compute the primes, but unless you know by measurement that your application requires greater speed than the function given above, or you haven't enough memory to store the sieve, you should use this method, which is simple and hard to get wrong. If you want to know more about the Sieve of Eratosthenes, I modestly recommend the essay Programming with Prime Numbers at my blog.

but the OP already uses the sieve of Eratosthenes. they just start at 2*p, which doesn't change the complexity btw, since Python's list access is O(1) on average. — Will Ness, Aug 19 '14 at 09:29

Optimizing a prime number generator in Python

4 Answers4