The discussion and solutions at (Golf): Sieve of Eratosthenes may enlighten. The best "normal" answer was 47 characters:

sub sieve {
  sub p{$_[0],@_>1?p(grep$_%$_[0],@_):()}p 2..pop
}
[download]