El primo 1000000 en C++

Hace algunos días me encontré con http://projecteuler.net/ y me sentí un poco abrumado por la cantidad de problemas no triviales que hay. Es común escribir programas en el colegio que encuentren números primos, así que me dio curiosidad el problema de encontrar el número primo 10001. El problema del algoritmo tradicional para encontrar primos es que es muy tardado en un computador promedio. La verdad es que lo intenté de las dos formas (tradicional y mi manera) para el primo 10001 y mientras el algoritmo tradicional funcionó en aprox. 1 min, el nuevo algoritmo fue casi instantáneo. Parece poca la diferencia, sin embargo para primos más grandes se vuelve bastante importante. Mi referencia será el primo 1000000 que obtuve en aprox. 2.5 min.

Esta es mi propuesta: Un número primo es un entero positivo que tiene uno y sólo un divisor positivo distinto de 1. Para encontrar números primos entonces probamos divisibilidad. Si quisiéramos saber si el número 5 es primo, entonces deberíamos probar 5/2, 5/3, 5/4, 5/5, de donde concluimos que 5 sólo tiene un divisor positivo distinto de 1, i.e. el mismo 5. Entonces para cualquier número natural p, debemos probar p/i con 1<i<p. Si i es divisor de p, entonces p no es un número primo (o bien es un número compuesto).

Tal vez está de más decirlo, pero véase que de inmediato descartamos los p números pares (es importante recordarlo en el código)

Esa es la forma más general, pero, ¿por qué gastar nuestro tiempo revisando divisibilidad con i para 1<i<p si sabemos que para ${1<i\leq\frac{p}{2}}$ es suficiente? Es evidente que para ${i=\frac{p}{2}}$ se cumple ${\frac{p}{i}=\frac{p}{p/2}=2}$, por lo que al seguir aumentando i arriba de p/2 en el intervalo general, nunca se obtiene otro entero (el siguiente será el 1). Por ello a partir de ahora puede considerarse este intervalo.

Ya es un gran avance saber que i se restringe al intervalo ${1<i\leq\frac{p}{2}}$, pero veamos si podemos hacer más.

Todo número entero mayor a uno sólo tiene dos opciones, ser primo, o ser el producto de números primos (puedes utilizar inducción para demostrarlo). Por tanto si p no es un número primo, podríamos expresarlo por máximo como el producto de i*i en el intervalo que ya tenemos, es decir: ${p=i^2}$, pero entonces de aquí se sigue que ${i=\sqrt{p}}$.

Por tanto -con las restricciones que tenemos- concluimos que el mejor intervalo para probar divisibilidad para p es ${1<i\leq\sqrt{p}}$.

Éste fue un ejercicio divertido y curioso; no es necesariamente que sea lo más eficaz para saber cuál es el enésimo número primo p, sobre todo conforme p se vuelve más y más grande (¿Puedes explicar por qué?). Wolfram Mathematica, por ejemplo, da el enésimo número primo con la instrucción Prime[n], instantáneamente.

Finalmente lo importante no es el número, sino el procedimiento para obtenerlo, en este caso con C++ y no hay caso en por ejemplo almacenar números primos o cosas por el estilo (precisamente lo que busca el problema de Project Euler es resolverlo "a partir del suelo"). El programa utiliza ciclos y ese es uno de los principales limitantes, sin embargo aún puede haber formas de mejorarlo (¿puedes indicar alguna?). A continuación una forma de codificación del algoritmo en C++:

long long int big=1000000, cont=1, yes, p=3;
cout << "Calculando... Espera un momento";
for(int i=p; cont<big; i+=2)
{
       yes=1;
       for(int j=2; j<=i/j; j++)
       {
             if(i%j==0) { yes=0; break;}
       }
       if(yes!=0) {cont++; p=i;}
}
system("cls");
cout << "El primo " << big << " es " << p << endl;