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.