What you see below is actually a prime sieve that is written in a single statement. I have used as many tricks as I could think of to lower the number of characters. Note, this code only works on python 2.5 (as I am using the new ternary operator). I also know that this code give a deprecation warning, that is because I am using
1e3 instead of the longer 1000.Please feel free to leave a comment if you either have a shorter version, or an idea on how to make it shorter.
print[n for(n,l)in[((i,locals()['_[2]']) if i>1 else(0,[]))for i in range(1e3)]if n and(not l.__setitem__(slice(n*2,None,n),[(0,None)]*len(l[n*2::n])))]
Edit: After a little trip home on the bus, I have it down to 132 characters ^^.
print[n for(n,l)in[(i,vars()['_[2]'])for i in range(2,1e3)]if n and(l.__setitem__(slice(n*2-2,None,n),[(0,0)]*len(l[n*2-2::n]))!=0)]
Edit: Make that 128 characters
print[n for(n,l)in[(i,vars()['_[2]'])for i in range(1e3)]if n>1 and(l.__setitem__(slice(n*n,None,n),[(0,0)]*len(l[n*n::n]))!=0)]
Edit: 84 characters, though it is no longer a one line/one statement thing
z=range(1e3);p=(n for n in z if n>1)
for n in p:z[n*n::n]=[0]*len(z[n*n::n]);print n
Huzzah,
ReplyDeletetim@tim-imac:/tmp/ncss$ wc -c prime_*
146 prime_mine.py
153 prime_original.py
tim@tim-imac:/tmp/ncss$ cat prime_mine.py
print[n for(n,l)in[(((0,[]),(i,vars()['_[2]']))[i>1])for i in range(1e3)]if n and not l.__setitem__(slice(n*2,None,n),[(0,None)]*len(l[n*2::n]))]
Don't forget that you are counting the newline character there... So your solution is actually 145 characters long...
ReplyDeleteI am sorry to say though, I am down to 132 (after a trip on the bus).
I have updated the main article to reflect my new solution.
72 characters:
ReplyDelete_=lambda x:x and x[:1]+_([i for i in x if i%x[0]]);print _(range(2,1e3))
I should point out though that there is a limit to how high you can go with this one before you hit Python's maximum recursion depth...
It's also not one statement.
James: Although that is a nice solution, it is not exactly a prime sieve... It requires the use of the modulus operator (which the prime sieve alleviates). Though, due to how python is implemented, your method might still be faster (though it does suffer from the recursion problem.
ReplyDelete