Velario, puedes poner lo que tarda el código original de StraT en tu máquina para ver que mejora se consigue con la Criba de Eratosthenes en el  mismo ordenador?

Por supuesto.

Tiempos con el codigo original de StraT :
------------------------------------------------------------------------
Hay 78499 números primos del 0 al 1000000
La búsqueda de primos ha tardado 00:00:02.4659440 segundos

Hay 664580 números primos del 0 al 10000000
La búsqueda de primos ha tardado 00:01:02.6601400 segundos

Hay 5761456 números primos del 0 al 100000000
La búsqueda de primos ha tardado 00:28:55.4528680 segundos
------------------------------------------------------------------------

Tiempos con mi codigo :
------------------------------------------------------------------------
78499 numeros primos encontrados en 1000000
La búsqueda de primos ha tardado 00:00:00.3359050 segundos

664580 numeros primos encontrados en 10000000
La búsqueda de primos ha tardado 00:00:03.8081890 segundos

5761456 numeros primos encontrados en 100000000
La búsqueda de primos ha tardado 00:00:42.4601680 segundos
------------------------------------------------------------------------

Los tiempos son lo que tarda solo el calculo, sin mostrar los numeros por pantalla.

Saludos.  

 Yo hace tiempo estuve curioseando con C# también en el tema de calcular números primos.
Todas las implementaciones que hacia me parecían demasiado lentas así que me puse a buscar
información sobre el tema y dí con un enlace muy interesante :

http://www.codeproject.com/csharp/highspee...rimenumbers.asp

Probé esa implementación con el BitArray y quede pasmado por la diferencia de velocidad en el
calculo respecto a mis implementaciones.

Los datos hablan por si mismos. :

664580 números primos encontrados en 10000000
La búsqueda de primos ha tardado 3 segundos

5761456 números primos encontrados en 100000000
La búsqueda de primos ha tardado 43 segundos

Claro está estas cifras son haciendo solo el calculo, si al código le añadimos un WriteLine para que
vaya mostrando los primos encontrados por pantalla, el tiempo aumenta estando sujeto a lo que
tarde en mostrar los números por el terminal.

Algunos datos mas de interés:

Procesador : Athlon64 3200+
Memoria : 2G de RAM
Sistema : Linux
Mono JIT compiler version 1.1.10 (Sin ninguna optimización añadida)

Saludos.