Python prime generator in one-line

That's not the Sieve of Eratosthenes, even though it looks like it is. It is in fact much worse. The Sieve is the best algorithm for finding primes.

See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

edit: I've modified https://stackoverflow.com/a/9302299/711085 to be a one-liner (originally it was not the real Sieve, but now it is... probably...):

reduce( (lambda r,x: r-set(range(x**2,N,x)) if (x in r) else r), 
        range(2,N), set(range(2,N)))

Demo:

>>> primesUpTo(N): lambda N: reduce(...)
>>> primesUpTo(30)
{2, 3, 5, 7, 11, 13, 17, 19}

---

Sadly I think that while this would be efficient in a functional programming language, it might not be as efficient in python due to non-persistent (shared-state and immutable) data structures, and any sieve in python would need to use mutation to achieve comparable performance. We can still cram it into a one-liner if we desperately wanted to. But first...

Normal sieve:

>>> N = 100
>>> table = list(range(N))
>>> for i in range(2,int(N**0.5)+1):
...     if table[i]:
...         for mult in range(i**2,N,i):
...             table[mult] = False
... 
>>> primes = [p for p in table if p][1:]
>>> primes
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

We can now define and call anonymous functions on the same line, as well as the hack of [...].__setitem__ to do inline mutation, and the hack of ... and foo to evaluate ... while returning foo:

>>> primesUpTo = lambda N: (lambda table: [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] for i in range(2,int(N**0.5)+1) if table[i]] and [p for p in table if p][1:])(list(range(N)))
>>> primesUpTo(30)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Proceed to cringe in horror, the one-liner expanded (oddly beautiful because you could almost directly translate the control flow, yet a terrible abuse of everything):

lambda N:
    (lambda table: 
        [[table.__setitem__(mult,False) for mult in range(i**2,N,i)] 
            for i in range(2,int(N**0.5)+1) if table[i]] 
        and [p for p in table if p][1:]
    )(list(range(N)))

This one-liner mutating version gave up at around 10⁸ on my machine, while the original mutating version gave up at around 10⁹, running out of memory (oddly).

The original reduce version gave up at 10⁷. So perhaps it is not that inefficient after all (at least for numbers you can deal with on your computer).

edit2 It seems you can abuse side-effects more concisely as:

reduce( (lambda r,x: (r.difference_update(range(x**2,N,x)) or r)
                     if (x in r) else r), 
        range(2,N), set(range(2,N)))

It gives up at around 10⁸, the same as the one-liner mutating version.

edit3: This runs at O(N) empirical complexity, whereas without the difference_update it ran at O(n^2.2) complexity.

Limiting the range that is reduced over, to the sqrt of the upper limit, and working with odds only, both result in additional speed-ups (2x and 1.6x correspondingly):

reduce( (lambda r,x: (r.difference_update(range(x*x,N,2*x)) or r)
                     if (x in r) else r), 
        range(3, int((N+1)**0.5+1), 2),
        set([2] + range(3,N,2)))

You can't check products of numbers only up to the square root to test for a prime. Look at 8- the square root of 8 is 2.8, so it will never try 4 * 2. (Indeed, the only numbers that wouldn't be seen as primes are square numbers).

ETA: Instead of trying all possible combinations of j and k, why not check if i is divisible by each j (using i % j == 0) up to the square root of j? This both takes less code and is much more efficient (though it is still not nearly as efficient as the Sieve of Eratosthenes).

Here's what you wanted:

def primes (q) :
 # return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,i)])
 # return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i) for k in xrange(1,j+1)])
 # return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i/2+1) for k in xrange(1,j+1)])

 return (i for i in xrange(2,q) if i not in [j*k for j in xrange(1,i/2+1) for k in xrange(1,min(j+1,i/j+1))])

In Haskell, the ranges are inclusive, so primes(542) is

[n | n<-[2..541], not $ elem n [j*k | j<-[1..n-1],     k<-[1..n-1]]]  --  25.66s
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n-1],     k<-[1..j]]]    --  15.30s
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n`div`2], k<-[1..j]]]    --   6.00s
                                                                      --   0.79s
[n | n<-[2..541], not $ elem n [j*k | j<-[1..n`div`2], k<-[1..min j (n`div`j)]]] 

And actually, 1*x == x so 1 isn't needed as a multiplier, thus it should be

[n | n<-[2..541], not $ elem n [j*k | j<-[2..n`div`2], k<-[2..min j (n`div`j)]]] 

which takes only 0.59 seconds. Or, in Python,

def primes (q) :
 return (i for i in xrange(2,q) if i not in [j*k for j in xrange(2,i/2+1) for k in xrange(2,min(j+1,i/j+1))])

---

update: for some reason, min j ... doesn't make much of a difference, in Haskell at least. So the expression becomes simply

[n | n<-[2..541], not $ elem n [j*k | j<-[2..n`div`2], k<-[2..n`div`j]]]