The following expression generates the list of prime numbers strictly inferior to a given positive integer N.
1 2 3 4
N = 40 [p for p in range(2,N) if 0 not in [p%d for d in range(2,p)]] # --> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
This uses a nested list comprehension : the outer list browses the prime candidate from 2 to N-1 under the name 'p'; the inner list computes all the remainders of the division of p by d where d goes from 2 to p-1. If at least one remainder is 0, then p is not prime since it is divisible by some d. Therefore, the condition 'if 0 not in' on the inner list selects the primes.
Here is a variant, which slightly longer to spell :
[p for p in range(2,N) if not [0 for d in range(2,p) if p%d==0]]
Here, the main condition is inside the inner list, which contains as many elements as p has divisors (incidentally, these elements are all 0, but any other value is fine). Hence, p is prime if and only if the inner list is empty, which is tested by a simple 'not [...]'.
These methods of generating prime numbers are clearly very inefficient compared to a more orthodox program but the challenge here is in writing the smaller program or expression that does the job. These expressions themselves may be improved easily for the sake of speed performance, but at the cost of a longer expression. Here are some ideas : - replace 'range(2,p)' by 'range(2,p/2+1)', - replace 'range(2,p)' by 'int(sqrt(p))+1)' (sqrt is imported from the math module), - replace 'range(...)' by 'xrange(...)', in both places.