Here's (nearly) the best I can do with the Sieve of Erastothenes:
(a) no need to initialize the array
(b) only checks odd numbers
(c) only marks odd increments of a found prime
(d) doesn't bother marking a found prime
Aside from changing algorithms, do you see a way to improve that?