Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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
share|improve this question

migrated from stackoverflow.com Jul 16 '13 at 4:17

This question came from our site for professional and enthusiast programmers.

1  
See stackoverflow.com/questions/567222/… –  maxwellb Jul 16 '13 at 4:04
    
    
But immediately: use True and False, not 'true' and 'false'. And use not prime and and prime. –  minitech Jul 16 '13 at 4:08
    

4 Answers 4

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):
        candidate +=2
        if isPrime(primes, candidate):
            primes.append(candidate)

    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.

share|improve this answer
    
+1 for near identical solutions :) Fantastic to see an iterative approach to primeList against the similar recursive one in my answer. Thanks! –  Nick Burns Jul 16 '13 at 5:18
    
This code does not run ideone.com/v6cOLI. j is not defined in the function isprime. Also why are not just returning when it is non-prime. It seems like a waste to use a variable to do essentially the same thing. –  Aseem Bansal Jul 17 '13 at 3:47
    
Thanks @AseemBansal. I had no idea that a site like ideone.com existed. That will be very useful. Very good point about not just returning, and I got rid of the while loop as well. Also I have no idea why I named the list inside primeList the same as the function. –  DominicMcDonnell Jul 17 '13 at 4:15

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.

share|improve this answer

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.

share|improve this answer
    
It fails for k = 1001. It isn't really that big a number. So that recursive approach won't work for even moderate numbers. ideone.com/k4u9So –  Aseem Bansal Jul 17 '13 at 3:54
    
You're right - and that is why the caveat is there in the last paragraph and a recommendation to use an iterative approach or a generator expression. –  Nick Burns Jul 17 '13 at 4:45
    
I tested this a bit more and it failed for all n > 312. ideone.com/jYliuH and ideone.com/dDgwiz This was a bit too much. Shouldn't the limit of recursion be more in Python? Your approach would be great in both clarity as well as speed in C as compilers optimize tail-recursive calls. In Python this flaw of tail-recursive calls not being optimized led to this being useless. –  Aseem Bansal Jul 17 '13 at 4:53
    
You don't seem to be considering the number of recursive calls necessary to generate 300 primes. It is far more than 300 calls because not all calls will generate a prime number. Again, the limits of recursion in Python have been discussed –  Nick Burns Jul 17 '13 at 4:58
    
I understand that there are more than 300 calls. Just saying that I didn't understand why this was so. I found that stack frames are big in Python and guido doesn't like tail-recursion but just... Anyways, me babbling doesn't help anyone so I'll stop with this. –  Aseem Bansal Jul 17 '13 at 5:03
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.

share|improve this answer
    
Avoiding the dots can give better timing.Your code timing was 0.25 and by avoiding dots it was 0.17. –  Aseem Bansal Jul 17 '13 at 4:43
    
@AseemBansal no, your testing is unreliable, because you chose too small a test size so it runs too fast, so you can't be sure whether you observe a real phenomenon or just some fluctuations. I tested this code for 100,000 primes, and there was no change in timing. OTOH even on the same code it was 3.75s usually but there was a one-time outlier of 4.20 (yes I ran it several times, to be sure my observation was repeatable). Another thing, my code performs its steps in correct sequence. It doesn't test any prime above the square root of the candidate. :) –  Will Ness Jul 17 '13 at 6:07
    
I wrote that in that sequence because I thought that would be better as there are more chances of a number being composite. I thought that benefit would build up. About the dots, I don't know why the Python Performance tips say that it helps the performance if they don't. About unreliable timing, noone is answering this question so I am stuck with using ideone for doing the timing. –  Aseem Bansal Jul 17 '13 at 7:22
    
@AseemBansal Ideone's fine, just short timespans (smaller than half a second, say) are not so reliable, a priori. --- ok, so your ordering saves one comparison for each composite, mine saves one division for each prime. –  Will Ness Jul 17 '13 at 12:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.