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.

Solution 1

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)

Solution 2

The Sieve of Eratosthenes is a good place to start.

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

Solution 3

Sieve of Eratosthenes is good.

Solution 4

The usual answer is to implement the Sieve of Eratosthenes, but this is really only a solution for finding the list of all prime numbers smaller than N. If you want primality tests for specific numbers, there are better choices for large numbers.

View more solutions

Comments

[Curd]

3. Well, you shouldn't drop all of them! You shouldn't drop 2 ;-)

[Juan Carlos Oropeza]

I think first statement is wrong. For example N = 120. 113 is prime < N. but 113 > sqrt (N).

[Wayne]

I'm not sure what you're trying to say. Of course there could be (unrelated) primes greater than the square root of N, but that doesn't tell us anything useful. The point is that every composite number has at least one prime factor less than or equal to its square root and you only need to find one such factor to prove that N is composite (i.e. there's no need to continue checking). That's the point of the first statement.

[Juan Carlos Oropeza]

Sorry. I think is maybe your answer is short and looks like a comment instead of a complete answer. When i read the Wiki Sieve of Eratosthenes I understand your tip. But because your answer was first thing I read didn't understand what was you talking about.

[Wayne]

The Sieve of Eratosthenes is not necessary for understanding the mathematical fact that all composite numbers have at least one prime factor less than or equal to their square root. My answer has nothing to do with the Sieve of Eratosthenes. What I'm describing is a method for eliminating many iterations when checking for primes. I'm afraid your comments here are not helping.

[Juan Carlos Oropeza]

You are correct, But you need to understand the context to apply that fact. I'm not saying your answer is wrong, but I didnt understand it until I got the context from the other answer I was just suggesting to improve your answer a little bit so other users get a better understanding, for example I confuse your N with OP M. Also just realize even when your was the accepted answer the one from Andrew is the most voted because give othrer users looking for answer the right context.

[HopefullyHelpful]

There are other sieves that are easy to understand and don't demand O(n) space. Or you just do it for a constant amount of numbers over and over. Eg. you want all primes below 10000 then do it in batches of 100 or 1000 to reduce space usage and only save the primes afterwards.

[Krish Bhanushali]

O(n) space is a lot of space complexity if N is higher, may be 2 billion or more than that. The Sieve of Atkin is the best to use.

[Admin]

This does not answer the question.