Python prime number function populating list

Question

so I can do this a simpler way, but I'm practicing with Pure Functions involving lists and I can't get this to work. I know i'm cheating and making it nonexact by not mentioning things like excluding 1 and not saving processesing time by only tabulating odd numbers but that's not my focus here. Pointers?

def is_prime(n):
    for i in range(2, n+1):
        if n % i == 0:
            return False
    return True

def listprimes_upto(n):
    result = []
    for i in range(2, n):
        if is_prime(i):
            result.append(i)
    return result

print(listprimes_upto(50))

(here's the easier non-list version that works fine):

def listprimesupto(n):
    for p in range(2, n+1):
        for i in range(2, p):
            if p % i ==0:
                break
        else:
            print(p)  

listprimesupto(50)

Pure functions involving lists? Are you talking about pure functions in the functional programming sense? — Shashank, Apr 08 '15 at 19:47

score 0 · Answer 1 · answered Apr 08 '15 at 19:35

Your is_prime is wrong. You must use range(2,n), otherwise you will always get False from the function. Because, obviously, the last i in the range will be n and n % i == 0.

def is_prime(n):
    #                vvv n here, not n+1
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

score 0 · Answer 2 · answered Apr 08 '15 at 19:38

0

Try this, 10x times efficient than your code when you use big numbers.

def is_prime(n):
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

def listprimes_upto(n):
    result = []
    for i in range(2, n):
        if is_prime(i):
            result.append(i)
    return result

print(listprimes_upto(50))

answered Apr 08 '15 at 19:38

Sailesh Kotha

1,939
3
20
27

And to generate the prime numbers list, we can just use `[i for i in range(2, 50) if is_prime(i)]` – AdmiralWen Apr 08 '15 at 19:47
@SpicyClubSauce yea, `efficiency` matters in this world. Implement this http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes algorithm in your code. Its much quicker, and its dynamic programming. – Sailesh Kotha Apr 08 '15 at 19:52

score 0 · Answer 3 · edited May 23 '17 at 12:28

See Sieve of Eratosthenes - Finding Primes Python

The Sieve of Eratosthenes is a much faster approach to finding primes.

this seems to be the fastest solution for finding primes in Python. There are also many other examples on this page of different ways of implementing functions to find prime numbers, although none of those examples create a second is_prime function leaving that as an exercise for you to figure out.

Python prime number function populating list

3 Answers3