find primes up to N For all numbers a : from 2 to sqrt(n) IF a is unmarked THEN a is prime For all multiples of a (a < n) mark multiples of as composite All unmarked nummbers are prime!