Generating a list of primes of a given length

Question

After considerable effort, I've come up with the following code to generate a list of primes of a given length.

I would be very interested to see how an experienced coder would modify my code to make it more readable, more concise, or somehow better. I won't be able to follow fancy-pants coding that doesn't involve basic iterations of the type I have used, so please keep it simple for me. I've been learning the language only a few months.

Function returns number of primes indicated in call.

Algorithm: Add two to last candidate in list (starting with [2, 3, 5]) and check whether other members divide the new candidate, iterating only up to the square root of the candidate.

import math
def primeList(listLength):
    plist = [2, 3]
    j = 3
    while listLength > len(plist):
        prime = 'true'
        i = 0
        j +=2
        plist.append(j)
        while plist[i] <= math.sqrt(j) and prime == 'true':
            if j%plist[i] == 0:
                prime = 'false'
            i +=1
        if prime == 'false':
            plist.pop(-1)         
    return plist

Answer 1

Don't be afraid of typing. Longer names are more readable and should be used except for simple counters. Split out complicated sub-parts where they are separate concepts.

Here is how I would improve it:

import math

def isPrime (primeList, candidate):
    upperLimit = math.sqrt(candidate)
    for p in primeList:
        if candidate % p == 0:
            return False
        if p >= upperLimit:
            break

    return True

def primeList(listLength):
    if listLength < 1 :
        return []
    primes = [2]

    candidate = 3
    while listLength > len(primes):
        if isPrime(primes, candidate):
            primes.append(candidate)
        candidate +=2

    return primes

To make a faster simple prime algorithm, consider the other naive algorithm in the primality test wikipedia article where all primes are of the form 6k +- 1.

Answer 2

I'll firstly talk about micro-optimizations then go for major optimizations that can be done in your code.

Don't use the while loop when you can instead use for i in xrange(). It is very slow. Take a look here and here. There are some limitations butxrange unless you are hitting that limit your code would get faster.

The inner while loop's conditions can be improved. As you have placed calculating math.sqrt() in the conditions it is calculated every time. That makes it very slow because finding square root consumes much time. You should use a variable before the loop to store that value. The second condition is not needed. Instead of checking always for the value of prime you can delete this condition as well as the variable and simply use a break in the if statement.

About using append. You are appending numbers and popping them if they are not primes. Not needed. Just append at the correct condition and use break

Also read the Python performance tips link given in Python Tags' wiki on codereview. I would have written it like this:

import math
def primeList(listLength):
    if listLength < 1:
        return []
    plist = [2]
    j = 3
    sqr_root = math.sqrt
    list_app = plist.append
    while listLength > len(plist):
        temp = sqr_root(j)
        for i in xrange(len(plist)):
            if j % plist[i] == 0:
                break
            if plist[i] > temp:
                list_app(j)
                break

        j += 2
    return plist

Notice that I defined math.sqrt as something. You'll find that in the Python Performance tips. Also your implementation had a bug. If I entered anything less than 2 it returned [2, 3] which was incorrect result.

This worked in 44 % time that your original function took. Your code's timing and my code's timing. Note that memory usage is lower in my case. I changed my code a bit. This new code uses only 34% time of OP's code.

Now done with micro-optimizations I'll get to major optimizations.

Using this approach to find the list of prime numbers is actually very naive. I also used it in the beginning and after much headache and waiting for outputs to come I found that such approaches can be very slow. Nothing you change in Python's syntax can offset the advantage of using a better algorithm. Check out this. It is not to difficult to implement. You can look at my github to get a basic implementation. You'll have to tweak it but you won't have to write it from the beginning.

Hope this helped.

Answer 3

Other than the few things pointed out above, it might be 'cleaner' to use a helper function to test primality. For example:

import math

def is_prime(x, primes):
    return all(x % i for i in primes if i < math.sqrt(x))

def first_k_primes(i, k, my_primes):
    if k <= 0:
        return my_primes

    if is_prime(i, my_primes):
        my_primes.append(i)   
        return first_k_primes(i + 2, k - 1, my_primes)

    return first_k_primes(i + 2, k, my_primes)

print(first_k_primes(5, 10, [2, 3]))

Now, I know you didn't want any "fancy-pants" coding, but this is actually really really similar to your iterative approach, just using recursion. If we look at each bit we have the following:

is_prime(x, primes): this tests whether the value x is prime or not. Just like in your code, it takes the modulo of x against all of the primes up to the square root of x. This isn't too tricky :) The all() function gathers all of these tests and returns a boolean (True or False). If all of the test (from 2 up to sqrt(x)) are False (i.e., every single test confirms ti is prime) then it returns this finding, and we know x is prime.

first_k_primes(i, k, my_primes): ok, this is recursive, but it isn't too tricky. It takes 3 parameters:

• i: the number to test
• k: the number of primes you still need to find until you have the number you want, e.g. if you want the first 4 primes, and you already know [2, 3, 5], then k will be 1
• my_primes: which is the list of primes so far.

In python, the first thing you need to do with a recursive function, is to figure out a base case. Here, we want to keep going until we have k number of primes (or until k = 0), so that is our base case.

Then we test to see if i is prime or not. If it is, we add it to our growing list of my_primes. Then, we go to the next value to test (i += 2), we can reduce k by one (since we just added a new prime) and we continue to grow our list of my_primes by calling the modified: first_k_primes(i + 2, k - 1, my_primes).

Finally, if it happens that i is not prime, we don't want to add anything to my_primes and all we want to do is test the next value of i. This is what the last return statement does. It will only get this far if we still want more primes (i.e. k is not 0) or i wasn't prime.

Why do I think this is more readable? The main thing is that I think it is good practice to separate out your logic. is_prime() does one thing and one thing only, and it does the very thing it says it does - it tests a value. Similarly first_k_primes() does exactly what it says it does too, it returns the first k primes. The really nice thing, is that this all boils down to one simple test:

if is_prime(i, my_primes):
    my_primes.append(i)

the rest just sets up the boundaries (i.e. the kth limit). So once you have seen a bit of recursion, you intuitively zoom in on the important lines and sort of 'ignore' the rest :)

As a side note, there is a slight gotcha with using recursion in Python: Python has a recursion limit of 1,000 calls. So if you need to recurse on large numbers it will often fail. I love recursion, it is quite an elegant way to do things. But it might also be just as easy to do the first_k_primes() function as an iterative function, or using a generator.

Answer 4

import math
def primeList(n):
    plist = [2, 3]
    j = 3
    while len(plist) < n:
        j += 2
        lim = math.sqrt(j)
        for p in plist:     # 100k primes: 3.75s vs 5.25 with while loop
            if p > lim:                    # and the setting of the flag, 
                plist.append(j)            # on ideone - dNLYD3
                break
            if j % p == 0:
                break
    return plist
print primeList(100000)[-1]    

Don't use long variable names, they hamper readability. Do add comments at first use site of a var to explain what it is (if not self-evident). Move repeated calculations out of the (inner) loop. No need to index into the plist list; just for ... in it.