Here is pseudocode for the Sieve of Eratosthenes:
function sieve(n):
isPrime = array of size (n+1), all true
isPrime[0] = isPrime[1] = false
for p from 2 to sqrt(n):
if isPrime[p]:
# mark all multiples of p as composite
for multiple from p*p to n step p:
isPrime[multiple] = false
# collect all primes
primes = []
for i from 2 to n:
if isPrime[i]:
primes.append(i)
return primes
Time complexity: O(n log log n). Space: O(n). This is much faster than testing each number individually.