From: Silvennoinen Sami <zam@cc.tut.fi>
Subject: Re: Smallest sieve??
Date: 3 Oct 1999 18:41:42 GMT
Newsgroups: sci.math
Keywords: C, perl codes to generate lists of primes

Well, check out my **obfuscated** prime generator written by perl:

for(2..$ARGV[0]){$$=1;for(0..@)-1){$][$_]=$$=0if++$][$
_]==$)[$_]}$)[@)]=$_,$][@]]=0,print++$",":\t$_\n"if$$}

This script prints out all the primes not exceeding its argument, i.e.,
	perl primes.pl 1000
lists all primes <=1000. 

(As you can see, it's not a sieve, but it generates primes alright)


Peter Gunn <petergunn@nospamhotmail.com> wrote:
: Ive just discovered Euler's Pentagonal Numbers and his
: formula for calculating the sum of the divisors of a number
: without factoring :-)

: And Ive written the following program which must surely be
: the worlds smallest prime generator??

: #include <stdio.h>

: #define TABLE_SZ 65538
: long tab[TABLE_SZ];

: long o(long n)
: {
:  long c=0,p=0,t=0,s=-1;
:  while (1)
:  {
:   s=-1*s; c=1-c; p=(3*c*c-c)>>1;
:   if (n-p<=0) break;
:   t+=s*tab[n-p];
:   c=0-c; p=(3*c*c-c)>>1;
:   if (n-p<=0) break;
:   t+=s*tab[n-p];
:  }
:  if (n-p==0)
:   t+=s*n;
:  return t;
: }


: main(int argc,char **argv)
: {
:  long q;

:  for (q=1;q<TABLE_SZ;q++)
:   tab[q]=o(q);

:  printf("1 is prime\n");
:  for (q=1;q<TABLE_SZ;q++)
:  {
:   if (tab[q]==q+1)
:    printf("%ld is prime\n",q);
:  }
: }

==============================================================================

From: "Adrian Cable" <megalith@jimc.demon.co.uk>
Subject: Re: Smallest sieve??
Date: Wed, 6 Oct 1999 17:03:05 +0100
Newsgroups: sci.math

> And Ive written the following program which must surely be
> the worlds smallest prime generator??
>
> #include <stdio.h>

[cut]

This may be the world's smallest prime number generator. However, I would
say that this is extremely unlikely, given that I just knocked this up in a
couple of mins, which prints out the primes from 2 to 10000.

main(){for(int i=2;i<=10000;i++){int k=0;for(int j=2;j<i;j++)k+=i%j==0?1:0;
(!k)?(printf("%d ",i)):0;}}

Enjoy. :)

Cheers,
Adrian Cable.

==============================================================================

From: Phil Carmody <carmody@cpd.ntc.nokia.com>
Subject: Re: Smallest sieve??
Date: Fri, 08 Oct 1999 19:04:59 +0100
Newsgroups: sci.math

Adrian Cable wrote:
[as above --djr]

which was shorter, but much easier to understand than the perl one (woo!)

However, the one-line answer was...

int i=1,j;main(){while(i++<10000)for(j=2;j*j<=i?i%j:!printf("%d ",i);++j);}

which, having fewer characters runs much faster too...

:-)


-- 
Phil Carmody
Not speaking for or on behalf of Nokia Telecommunications
==============================================================================
[Save the last two lines to a file "p.pl", then issue  "perl p.l 1000" : --djr]

for(2..$ARGV[0]){$$=1;for(0..@)-1){$][$_]=$$=0if++$][$
_]==$)[$_]}$)[@)]=$_,$][@]]=0,print++$",":\t$_\n"if$$}