Shortest prime number program

[swisscheese]

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]

[Mitja Trampus]

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.

[swisscheese]

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]

[Ian Bygrave]

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

[Martin v. Löwis]

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]

[swisscheese]

>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]

[mensanator]

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)

[Ian Bygrave]

On Sat, 11 Feb 2006 12:43:23 +0000, 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

[Ian Bygrave]

On Sat, 11 Feb 2006 13:33:58 +0000, 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

[Grant Edwards]

On 2006-02-11, swisscheese <ji******@miclog.com> 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.com sandwich is HIT by a
TROLLEY-CAR...

[dickinsm]

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

[Christoph Zwerschke]

di******@gmail.com 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

[Jeffrey Schwab]

di******@gmail.com 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. :)

[swisscheese]

> [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.

[bearophileHUGS]

This is a little shorter :-)

[2]+[x for x in range(2,99)if 2**x%x==2]

Bye,
bearophile

[swisscheese]

> 42
Make that 41 and 40.

[Ralf Muschall]

Christoph Zwerschke wrote:

di******@gmail.com 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,... <insert all primes here>]+[x for x in range(1,99) if False]

For sufficiently small values of 99, this will also be a rather
short program.

[Tim Hochberg]

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

[Christoph Zwerschke]

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

[Tim Hochberg]

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