Re: Shortest prime number program
In the spirit of pointless pessimization and obfuscation I have crushed
something very similar to Alex Martelli's eratosthenes function onto a
single line. It's truly monstrous, but somewhat entertaining [Some
preemptive linebreaks added]:
def short():import itertools as it;D={};g=D.get;return (
q for q in it.count(2) if
D.__setitem__(it.dropwhile(D.__contains__,
xrange(g(q,q)+q,2**30,g(q,q))).next(),g(q,q))
or q not in D and D.pop(q,1))
I'm sure there's a lesson to this somewhere. Something like I need to
find something better to do with my spare time.
-tim
--
http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
Tim Hochberg wrote: > from itertools import count, ifilter > def sieve(s=count(2)): > while 1:p=s.next();s=ifilter(p.__rmod__,s);yield p Nice! -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
While not nearly the shortest proposed thus far, I'm fond of: from itertools import count, ifilter def sieve(s=count(2)): while 1:p=s.next();s=ifilter(p.__rmod__,s);yield p It will generate quite a large number of primes before blowing up (at least 50,000 primes, p=611,957) and it's much faster than the other submissions thus far that can generate a more or less arbitrary number of primes. It's still much slower than Alex Martelli's version in the cookbook though. [And yes I know that you can shave off one character by importing ifilter as i, but that's too much ick for too little gain. There may well be other, more fruitful ways to compact it though] -tim -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
Christoph Zwerschke wrote: > [EMAIL PROTECTED] schrieb: >> How about: >> [2]+[x for x in range(1,99) if 2**x%x==2] > If the range goes beyond 340, it also gives non-primes... [2,3]+[x for x in range(1,99) if 2**x%x==2 and 3**x%x==3] [2,3,5]+[x for x in range(1,99) if 2**x%x==2 and 3**x%x==3 and 5**x%x==5] SCNR, Ralf PS: They both break at 561, and further strengthening of the condition will not help. Manual loop unrolling as follows works: [2,3,... ]+[x for x in range(1,99) if False] For sufficiently small values of 99, this will also be a rather short program. -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
> 42 Make that 41 and 40. -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
This is a little shorter :-) [2]+[x for x in range(2,99)if 2**x%x==2] Bye, bearophile -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
> [2]+[x for x in range(1,99) if 2**x%x==2] 42 - brilliant! 41: [2]+[x for x in range(1,99)if 2**x%x==2] ... although it appears Christoph is right that it's not scalable. -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
[EMAIL PROTECTED] wrote: > swisscheese wrote: > >>r=range(2,99) >>m=[x*y for x in r for y in r] >>[x for x in r if not x in m] > > > How about: > > [2]+[x for x in range(1,99) if 2**x%x==2] 43. I'll be chewing on this one for a while. Thank you. :) -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
[EMAIL PROTECTED] schrieb: > How about: > > [2]+[x for x in range(1,99) if 2**x%x==2] If the range goes beyond 340, it also gives non-primes... -- Christoph -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
swisscheese wrote: > > r=range(2,99) > m=[x*y for x in r for y in r] > [x for x in r if not x in m] How about: [2]+[x for x in range(1,99) if 2**x%x==2] Mark -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
On 2006-02-11, swisscheese <[EMAIL PROTECTED]> wrote: >>You can save two bytes with > > 56 - nice catch. > 55: > r=range(2,99) > [x for x in r if sum(x%d<1 for d in r)<2] And if this were FORTRAN: r=range(2,99) [xforxinrifsum(x%d<1fordinr)<2] ;) -- Grant Edwards grante Yow! Hmmm... a CRIPPLED at ACCOUNTANT with a FALAFEL visi.comsandwich is HIT by a TROLLEY-CAR... -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
On Sat, 11 Feb 2006 13:33:58 +, Ian Bygrave wrote: > Well, given a hypothetical new function 'sieve' which should have been: def sieve(f,l): if not l: return l head,tail=l[0],l[1:] def filter_func(x): return f(x,head) tail=filter(filter_func,tail) return [head]+sieve(f,tail) > The prime generation can be reduced to: > > from operator import * > sieve(mod,range(2,99)) --Ian Bygrave -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
On Sat, 11 Feb 2006 12:43:23 +, Ian Bygrave wrote: > p,r=[],range(2,99) > while r:p,r=p+r[:1],[x for x in r if x%r[0]] > > And the result's in p. Well, given a hypothetical new function 'sieve' def sieve(f,l): if not l: return l head,tail=l[0],l[1:] def filter_func(x): return f(x,head) tail=filter(filter_func,tail) return [head]+tail The prime generation can be reduced to: from operator import * sieve(mod,range(2,99)) Is there any precedent for such a function, or any other uses? --Ian Bygrave -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
swisscheese wrote: > I figured someone out there must have written a minimal code size prime > number generator. I did not find one after a bit of searching around. > For primes up to 100 the best I could do was 70 characters (including > spaces): > > r=range(2,99) > m=[x*y for x in r for y in r] > [x for x in r if not x in m] import gmpy p=2 while p<99:p=gmpy.next_prime(p) -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
>You can save two bytes with 56 - nice catch. 55: r=range(2,99) [x for x in r if sum(x%d<1 for d in r)<2] -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
You can save two bytes with r=range(2,99) [x for x in r if sum(x%d==0 for d in r)<2] -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
On Sat, 11 Feb 2006 02:03:46 -0800, swisscheese wrote: > I figured someone out there must have written a minimal code size prime > number generator. I did not find one after a bit of searching around. > For primes up to 100 the best I could do was 70 characters (including > spaces): > > r=range(2,99) > m=[x*y for x in r for y in r] > [x for x in r if not x in m] I swore I'd never play Python golf. p,r=[],range(2,99) while r:p,r=p+r[:1],[x for x in r if x%r[0]] And the result's in p. --Ian Bygrave -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
At 58, very nice :-) Building on yours we get 57: r=range(2,99) [x for x in r if sum([x%d==0 for d in r])<2] -- http://mail.python.org/mailman/listinfo/python-list
Re: Shortest prime number program
swisscheese wrote: > I figured someone out there must have written a minimal code size prime > number generator. I did not find one after a bit of searching around. > For primes up to 100 the best I could do was 70 characters (including > spaces): > > r=range(2,99) > m=[x*y for x in r for y in r] > [x for x in r if not x in m] A more straightforward and somewhat shorter solution: r=range(2,99) [x for x in r if [x%d for d in r].count(0)<2] I'm sure it can be made shorter still. -- http://mail.python.org/mailman/listinfo/python-list
Shortest prime number program
I figured someone out there must have written a minimal code size prime number generator. I did not find one after a bit of searching around. For primes up to 100 the best I could do was 70 characters (including spaces): r=range(2,99) m=[x*y for x in r for y in r] [x for x in r if not x in m] -- http://mail.python.org/mailman/listinfo/python-list
