Sieve - Implementation

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.