Find prime numbers with list comprehension

Question

I was trying to write a code to select the prime numbers in a list. The user gives a limit and the program displays all prime number from 2 to the limit. I was trying to reduce the maximum amount of lines I could and was surprised with some situations I can't understand. If you can help me, I'd be grateful.

I wrote this code:

# returns all integers from 2 to a limit given by the user. 

def primes(limit):
    # generates the numbers. 
    lista = range(2, limit + 1)
    
    p = 2
    
    while p < limit:
        #filters the prime numbers and places in a list.
        lista = [i for i in lista if i == p or i % p != 0]
    
        p += 1
    

    return lista

        
def main():
    #asks the user for the limit number.
    l = int(input("Enter the limit: "))
    
    #call the function which selects the numbers and returns the result. 
    return print(primes(l))

#Ensures that the main program only runs when the functions have not been imported into another file.
if __name__ == '__main__':
    main()

It runs as I expected, but when I tried deleting the first list assignment line and include the range function directly into the comprehension, it doesn't work. Why?

# returns all integers from 2 to a limit given by the user. 

def primes(limit):
    p = 2
    
    while p < limit:
        #filters the prime numbers and places in a list.
        lista = [i for i in range(2, limit + 1) if i == p or i % p != 0]
    #or lista = [i for i in range(2, limit + 1) if i == p or i % p != 0]
    #or lista = [i for i in [*range(2, limit + 1)] if i == p or i % p != 0]
    
        p += 1
    

    return lista

        
def main():
    #asks the user for the limit number.
    l = int(input("Enter the limit: "))
    
    #call the function which selects the numbers and returns the result. 
    return print(primes(l))

#Ensures that the main program only runs when the functions have not been imported into another file.
if __name__ == '__main__':
    main()

Other problem. As the line with range is not a list I fixed it only to improve the code, but when I changed the name of the value from 'lista' to another name, I saw that it doesn't work too. Why?

# returns all integers from 2 to a limit given by the user. 

def primes(limit):
    # generates the numbers. 
    nums = range(2, limit + 1)

    p = 2
    
    while p < limit:
        #filters the prime numbers and places in a list.
        lista = [i for i in nums if i == p or i % p != 0]
    
        p += 1
    

    return lista

        
def main():
    #asks the user for the limit number.
    l = int(input("Enter the limit: "))
    
    #call the function which selects the numbers and returns the result. 
    return print(primes(l))

#ensures that the main program only runs when the functions have not been imported into another file.
if __name__ == '__main__':
    main()

Thanks for your attention.

It's because you modify `lista` in the `while p < limit` loop, so each time you run the loop the start sequence is different. When you change `lista` to `range(2, limit + 1)` or `nums`, you change the start sequence to a constant value, and your code will only filter out the multiples of the last `p` value. — Nick, Dec 05 '20 at 07:26
you need to see https://stackoverflow.com/help/someone-answers — coderoftheday, Dec 06 '20 at 13:09

score 0 · Answer 1 · answered Dec 05 '20 at 07:28

0

This one-liner works perfectly :

def primes(val):
    return [x for x in range(2, val) if all(x % y != 0 for y in range(2, x))]

print(primes(10))

answered Dec 05 '20 at 07:28

Yash Makan

706
1
5
17

Iran why wouldnt you accept the answer then? – adir abargil Dec 06 '20 at 05:44
Sure it works, but it's terribly inefficient. – Mark Ransom Dec 09 '20 at 04:21

Iran Santos · Accepted Answer · 2020-12-08T06:59:40.863

0

Thank you for your attention.I liked the answer of our friend Yash Makan, but when I tried larger numbers, like 100000, it never led me to the result (or I was not so patient to wait). So I continued thinking about the problem and got the following that is the fastest way to compute this problem I could achieve with list comprehension. Note how fast you can compute millions of numbers.

# returns all integers from 2 to a limit given by the user. 

def primes(limit):
    
    l = [i for i in range(2, limit + 1) if all(i % j != 0 for j in [2, 3, 5])]    
    lista = []
    return [2, 3, 5] + [lista.append(i) or i for i in l if all( i % j != 0 for j in lista[:int((len(lista) ** .5) + 1)])]

        
def main():
    l = int(input("Enter the limit: "))
    
    return print(primes(l))

if __name__ == '__main__':
    main()

edited Dec 08 '20 at 06:59

answered Dec 06 '20 at 02:42

Iran Santos

1
2

If you want to go twice as fast, replace `range(2, int(i**.5) + 1)` with `itertools.chain([2], range(3, int(i**.5) + 1, 2)`. Of course that's still not nearly as fast as a proper Sieve of Eratosthenes. – Mark Ransom Dec 06 '20 at 03:01
I tried the Sieve of Eratosthenes but it's not that good with realy big numbers. – Iran Santos Dec 07 '20 at 17:37
What does "not that good" mean? There are other ways to generate lists of primes, but the Sieve is a good compromise between simplicity and efficiency. – Mark Ransom Dec 07 '20 at 19:43
Not that good with very big numbers because it's not so fast. I could not write it in a list comprehension or find a faster way to do this. But if you know a way to write the Sieve of Eratosthenes with a list comprehension I would be very grateful. – Iran Santos Dec 08 '20 at 00:26
There are lots of posts on how to write a good Sieve, one I'm familiar with is https://stackoverflow.com/q/9301781/5987. I don't think it's possible with *just* a list comprehension, but if you search you may find one. – Mark Ransom Dec 08 '20 at 01:12

Find prime numbers with list comprehension

2 Answers2