Return all prime numbers smaller than M

Question

Given an integer M. return all prime numbers smaller than M.

Give a algorithm as good as you can. Need to consider time and space complexity.

Answer 1

The Sieve of Eratosthenes is a good place to start.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 2

A couple of additional performance hints:

1. You only need to test up to the square root of M, since every composite number has at least one prime factor less than or equal to its square root
2. You can cache known primes as you generate them and test subsequent numbers against only the numbers in this list (instead of every number below sqrt(M))
3. You can obviously skip even numbers (except for 2, of course)