Hace poco vi la de 1998, de la película de terror "el Cubo", en la que un personaje dice que es humanamente imposible determinar, con la mano sin necesidad de un ordenador, si son grandes (en la película de 3 dígitos) enteros son los principales poderes, es decir, que son divisibles por exactamente un número primo. Naturalmente, me decidí a tratar de trabajar este problema a mano en un papel.
En primer lugar, En orden a determinar si un número es una potencia principal, sólo necesitaba encontrar un primer factor. Por ejemplo, $5$ es un primer factor de $555$ (debido a $555 = 5*111$), pero el otro factor ($111$), no es divisible por cinco, por lo tanto, $555$ tiene más factores primos que sólo $5$, e $555$ no es una fuente primaria de energía.
Yo estaba en un principio sólo la comprobación de todos los números primos menor que el entero $L$, en fin, a ver si ellos eran los factores de $L$. Para números de 3 dígitos, esto no suele tomar mucho tiempo, pero si $L$ sí es un primo, entonces usted va a terminar la comprobación de que cada primer menos de $L$.
Así, la pregunta es: Dado un entero arbitrario $L$, si se realiza una búsqueda por fuerza bruta, la comprobación de que cada primer número de una lista, ¿cuál es el número mínimo de números primos tendrá que comprobar antes de que pudiera detenerse y a la conclusión de que $L$ es primo?
Me decidí a tratar de reducir el espacio de búsqueda. Si tengo un número primo $P$ donde $\frac{L}{2}<P<L$, luego de que el primer número no podía ser un factor de $L$, debido a $2P>\frac{2L}{2}$ o, $2P > L$. Del mismo modo, si $\frac{L}{3}<P<L$, entonces, una vez más, $P$ no podría ser un factor de $L$, debido a $3P > L$, y ya he comprobado que $2$ no es un factor de $L$, lo $2P ≠ L$. Usted puede hacer este mismo argumento para $\frac{L}{5}, \frac{L}{7}, \frac{L}{11}$, etc.
En otras palabras, no es necesario comprobar cada número primo, solo me falta comprobar todos los números primos hasta el punto de que $\frac{L}{P_{n}} < P_{n}$, ($P_{n}$ es el enésimo número primo) porque, en ese momento, todos los números primos antes de $P_{n}$ ha sido descartado, y desde $P_{n} > \frac{L}{P_{n}}$$(P_{n})^2 > L$, lo $P_{n}$ no es un factor de $L$. También, si $P_{n} > \frac{L}{P_{n}}$$P_{n + 1} > \frac{L}{P_{n + 1}}$, debido a $P_{n + 1} > P_{n}$, este mismo razonamiento se descarta todas las grandes números primos.
Así, por ejemplo, cuando se intenta encontrar un primer factor de $607$, más que la comprobación de que cada número primo menor que $607$, solo me falta comprobar el primero $10$ los números primos hasta el $29$, debido a $\frac{607}{29} < 29$. Si la primera $10$ de los números primos no son factores de $607$, $607$ no tiene factores primos y debe ser un primo.
Es mi razonamiento válido, y, es posible reducir el número de números primos que había necesidad de verificar aún más?
