La criba de Eratóstenes.

Los primos son los átomos de la aritmética: cada número se escribe como producto de primos de forma única. Eratóstenes, bibliotecario de Alejandría, encontró hace 2200 años una forma elegante de encontrarlos todos: tacha los múltiplos.

Primos encontrados

Pseudocódigo

function sieve(N):
  primes ← array[2..N], all true
  for p from 2 to √N:
    if primes[p]:
      for k from p² to N step p:
        primes[k] ← false
  return {p : primes[p]}

Complejidad O(N log log N). Casi lineal. Para los primeros mil millones: segundos.