Ok, how's 50 characters for the bonus:

sub sieve {
  grep!(map$_[$a*$_]++,1..$_[0]/($a=$_))[0],2..$_[0]
}
[download]

update: Hmm, in my golfing frenzy, I seem to have increased the big-O back to that of the main problem, so I don't think this qualifies after all.

   MeowChow                                   
               s aamecha.s a..a\u$&owag.print