Generating A List Of Prime Numbers Using List Comprehension

I'm trying to create a list of all the prime numbers less than or equal to a given number. I did that successfully using for loops. I was trying to achieve the same using list comp

Solution 1:

It simply doesn’t work that way. List comprehensions are evaluated separately, so you can imagine it like this:

pr = [2]
tmp = [i for i in xrange(3,num+1) if not [x for x in pr if i%x==0]]
pr += tmp

By the time tmp is evaluated, pr only contains 2, so you only ever check if a number is divisible by 2 (i.e. if it’s even). That’s why you get all uneven numbers.

You simply can’t solve this nicely using list comprehensions.

---

† Not nicely, but ugly and in a very hackish way, by abusing that you can call functions inside a list comprehension:

pr = [2]
[pr.append(i) for i in xrange(3,num+1) if not [x for x in pr if i%x==0]]
print(pr) # [2, 3, 5, 7, 11, 13, 17, 19]

This abuses list comprehensions and basically collects a None value for each prime number you add to pr. So it’s essentially like your normal for loop except that we unnecessarily collect None values in a list… so you should rather allow yourself to use a line break and just use a normal loop.

Solution 2:

Your list pr doesn't update until after your entire list comprehension is done. This means your list only contains 2, so every number dividable by 2 is not in the list (as you can see). You should update the list whenever you found a new prime number.

Solution 3:

This is because the pr += [...] is evaluated approximately as this:

pr = [2]
tmp = [i for i in xrange(3,num+1) if not [x for x in pr if i%x==0]]
pr.extend(tmp) 

So while tmp is generated, contents of pr remains the same ([2]).

I would go with function like this:

>>> import itertools
>>> def primes():
...     results = []
...     for i in itertools.count(2):
...         if all(i%x != 0 for x in results):
...             results.append(i)
...             yield i
...
# And then you can fetch first 10 primes
>>> list(itertools.islice(primes(), 10))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
# Or get primes smaller than X
>>> list(itertools.takewhile(lambda x: x < 50, primes()))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Note, that using all is more efficient than creating array and testing whether it's empty.