Re: (Golf): Sieve of Eratosthenes

Here is one of 68 characters in length:

sub p{my@x;map{my$c=$_;$_%$c||++$x[$_]for@_}@_=2..pop;grep$x[$_]==1,0.
+.$#x}
[download]

UPDATE: And another of 65:

sub p{@_=2..pop;my$c;while($_[$c]){@_=($_[$c],grep$_%$_[$c],@_);$c++}@
+_}
[download]

UPDATE: And another of 60:

sub p{@_=2..pop;my$c;@_=($_[$c++],grep$_%$_[$c-1],@_)while$c<@_;@_}
[download]

UPDATE: And another of 40 (but I fear it strays from the rules...):

sub p{grep{my$c=$_;$#_==grep$c%$_,@_}@_=2..pop}
[download]

japhy -- Perl and Regex Hacker

Comment on Re: (Golf): Sieve of Eratosthenes Select or Download Code

Replies are listed 'Best First'.

Re (tilly) 1: (Golf): Sieve of Eratosthenes
by tilly (Archbishop) on May 19, 2001 at 18:40 UTC

Basically you reversed the role of the 2 loops.

The 60 character answer is impressive. However it seems to scale quadratically. I must confess that I don't see why it is scaling quadratically, but it clearly is. So unless you can explain why this is a bug in Perl, I am going to have to call this a solution to only the first problem.

UPDATE
I now understand why your 60 character solution is scaling slowly. It actually scales like O(n*n/log(n)), and it is because you are walking all of the primes with each strike rather than just the multiples of the current prime. So it definitely only is a solution to the first problem.

[reply]


Do you know where your variables are?
	PerlMonks