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]

Re: Shortest prime number program

swisscheese wrote:[color=blue]
> 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][/color]

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]

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]

[Ian Bygrave]

Re: Shortest prime number program

On Sat, 11 Feb 2006 02:03:46 -0800, swisscheese wrote:
[color=blue]
> 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][/color]

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]

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]

[swisscheese]

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]

[mensanator@aol.com]

Re: Shortest prime number program


swisscheese wrote:[color=blue]
> 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][/color]

import gmpy
p=2
while p<99:p=gmpy.nex t_prime(p)

[Ian Bygrave]

Re: Shortest prime number program

On Sat, 11 Feb 2006 12:43:23 +0000, Ian Bygrave wrote:[color=blue]
> 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.[/color]

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(fil ter_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]

Re: Shortest prime number program

On Sat, 11 Feb 2006 13:33:58 +0000, Ian Bygrave wrote:
[color=blue]
> Well, given a hypothetical new function 'sieve'[/color]

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(fil ter_func,tail)
return [head]+sieve(f,tail)
[color=blue]
> The prime generation can be reduced to:
>
> from operator import *
> sieve(mod,range (2,99))[/color]

--Ian Bygrave

[Grant Edwards]

Re: Shortest prime number program

On 2006-02-11, swisscheese <jimlewis@miclo g.com> wrote:[color=blue][color=green]
>>You can save two bytes with[/color]
>
> 56 - nice catch.
> 55:
> r=range(2,99)
> [x for x in r if sum(x%d<1 for d in r)<2][/color]

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

Re: Shortest prime number program


swisscheese wrote:[color=blue]
>
> 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][/color]

How about:

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

Mark

[Christoph Zwerschke]

Re: Shortest prime number program

dickinsm@gmail. com schrieb:[color=blue]
> How about:
>
> [2]+[x for x in range(1,99) if 2**x%x==2][/color]

If the range goes beyond 340, it also gives non-primes...

-- Christoph

[Jeffrey Schwab]

Re: Shortest prime number program

dickinsm@gmail. com wrote:[color=blue]
> swisscheese wrote:
>[color=green]
>>r=range(2,9 9)
>>m=[x*y for x in r for y in r]
>>[x for x in r if not x in m][/color]
>
>
> How about:
>
> [2]+[x for x in range(1,99) if 2**x%x==2][/color]

43.

I'll be chewing on this one for a while. Thank you. :)

[swisscheese]

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.

[bearophileHUGS@lycos.com]

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