Compact Sieve of Eratosthenes in Python

Question

I need to implement the Sieve of Eratosthenes in Python, but wanted to implement it as compactly as possible due to its part in a large body of code. While there are much much more efficient ways to accomplish finding prime numbers, I wanted to see what Python could do for me in crazy compactness.

The program needs to ask the user for input and then output all prime numbers using a sieve from 2 to the input number, inclusive.

The best I can get so far is:

n = int(input("To what n do you wish to find primes? "))
sieve = list(range(2, n+1))
for i in range(len(sieve)):
    for j in range(i+1, len(sieve)):
        if sieve[i] == 0:
            continue
        if sieve[j] % sieve[i] == 0:
            sieve[j] = 0
print([i for i in sieve if i != 0])

Beyond that, I have trouble condensing the code further.

EDIT: Couldn't find the response that makes this one duplicate before asking this question because I was hung up on searching specifically for "Compact Sieve of Eratosthenes" and its variations. Thanks!

This is probably a better fit on either http://codereview.stackexchange.com/ or http://codegolf.stackexchange.com/ , depending on whether your primary goal is, "as compact as possible without being unreadable" or "as compact as possible, even if it becomes unreadable." — Brian, Oct 06 '14 at 14:35
http://bytes.com/topic/python/answers/455979-shortest-prime-number-program — Robᵩ, Oct 06 '14 at 14:40

score 0 · Answer 1 · answered Oct 06 '14 at 14:44

Here's what I came up with:

n = [False for i in range(int(input('> '))+1)]
n[0] = n[1] = True
for i in range(2, len(n)):
    for j in range(i+1, len(n)):
        n[j] = ((j % i) == 0) if not n[j] else n[j]
print([i for i in range(len(n)) if not n[i]])

Compact Sieve of Eratosthenes in Python

1 Answers1