Re: (Golf): Sieve of Eratosthenes

[chipmunk]

This solution is very similar to japhy's, although I started it without looking at his. I did use his solutions to inspire me to shorten mine, though!

57 characters:

sub sieve {
my@p;@_=2..pop;{push@p,$p=shift;redo if@_=grep$_%$p,@_}@p
}

58 characters, strict-compliant:

sub sieve {
my@p;@_=2..pop;{push@p,shift;redo if@_=grep$_%$p[-1],@_}@p
}

BTW, what is the Big-O of the Sieve of Eratosthenes? :)

[tilly]

The sieve of Eratosthenes is O(n*log(log(n))) arithmetic operations. Arithmetic operations themselves scale logarithmically officially there is another log operation in there. So within memory limits it should look basically linear in n. I might be willing to bend a log factor here or there. But if it isn't roughly linear in my tests, you don't qualify.

And BTW I am not worrying about strict.