Find prime numbers

There are many interesting results on this problem.

The naive method is testing odd factors up to n/2. It's O(n^2) though.
By eliminating multiples of 3, 5, 7 first you can eliminate about 70% of the numbers.
In testing, you can use square instead of square root to speed up calculation.

There are probabilistic algorithms, such as Rabin test, and Lehman test.

The Sieve of Atkin algorithm is described here. Cost is O((N/log) * log N) in time, and N^(1/2 + o(1)) in memory.

The sieve of Eratosthenes algorithm uses O(N) time and O(N^(1/2)(log (log N))/log N) memory.

BTW, the density of prime numbers around N is 1/ln(N). This translates to that the average gap between prime numbers around N is ln(N).