The following expression generates the list of prime numbers strictly inferior to a given positive integer N.
Download
Copy to clipboard1 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.
A faster version. Using this:
we only taste the divisors up to p/2. We can do this because d>p/2 will surely not yield an integer result. Speed increase for N=1000 on my Athlon 1333: 38s instead of 77s or roughly factor 2.
... an addition. the above example is for illustration, not a critique of the original version
Another speedup (David Lees). It is only necessary to check odd numbers after 2, so a 2X speedup can be achieved by having the first range statement step by two like this:
[p for p in range(3,N,2) if 0 not in [p%d for d in range(2,p)]]
A minor penalty is that the number 2 is not generated as the first prime.
More entries in the speed-up game. Instead of checking all odd divisors, how about checking only prime divisors that are half or less than the candidate:
If you're careful, psuedo-prime testing can speed-up the process even more: