Commodore 64 Basic, 55 characters
Incredibly slow: first, because the algorithm is extremely inefficient (it tries dividing by every value less than half the candidate number), second, because the Commodore 64 is slow, and third, because Commodore Basic does all its math in emulated floating-point on an 8-bit CPU.
Theoretical solution, 82 characters
If this program could run on an actual Commodore 64, it would be much faster than the above. However, it can't: the sieve alone would take 5,000,007 bytes out of the 38,911 bytes a C64 has available for Basic programs. Note the use of
-1 instead of
1 when denoting composite values in the array: C64 Basic doesn't have a true boolean negation;
NOT performs a two's complement instead.