¿Qué tan eficiente es el segundo algoritmo publicado en http://www.naturalnumbers.org/#ap: ‘a la Fermat’?

Answer 1

Esto se refiere al algo de “división trivial”.
=============
¿Polinomio en función de qué? La magnitud del límite superior? ¿O su longitud (número de dígitos)?

Un algoritmo de fuerza bruta para encontrar todos los divisores de [math] N [/ math] (y así verificar si [math] N [/ math] es primo) tendrá un tiempo de ejecución proporcional a [math] \ sqrt {N} [ /matemáticas].

Un algoritmo de fuerza bruta para encontrar todos los divisores de un número de dígitos [matemáticos] N [/ matemáticos] tendrá un tiempo de ejecución proporcional a [matemáticos] 10 ^ {N / 2} [/ matemáticos].

Actualización : Por “fuerza bruta”, por supuesto, me refería a un algoritmo ingenuo para probar principalmente por división. Consulte el artículo de Wikipedia sobre la prueba de Primality. En contraste con el algoritmo de división de prueba (que usa en su bucle interno), cuyo tiempo de ejecución no es polinómico en términos del tamaño (número de dígitos) de la entrada, existen pruebas de primalidad con tiempo de ejecución polinómico (prueba de primigenia AKS ) Sin embargo, como todavía itera a través de todos los números entre su mínimo y máximo, en términos de la cantidad de dígitos, su bucle externo seguirá realizando un número exponencial de iteraciones a medida que busca primos gemelos. Entonces, a menos que haya entendido mal algo en su pregunta y código, argumentaría que su algoritmo tiene un tiempo de ejecución no polinómico; Si agrego un dígito adicional a su variable “max”, el tiempo de ejecución aumenta en un factor de 10.

Answer 2

No, esta hoja de cálculo no muestra / prueba que encontrar primos gemelos es polinomial (aunque proporciona alguna evidencia de la posibilidad). Resulta que se sabe que la prueba de primalidad es determinísticamente polinomial, por lo que probar un par de números impares separados por dos para primalidad también es polinomial. Por una extensión muy simple, verificar todos los pares impares en secuencia es polinomial. Lo que su hoja de cálculo no muestra es una prueba de que la prueba de primalidad es polinómica (lo insinúa en la parte 3 de sus premisas).

Answer 3

Dado que solicitó mi opinión, y parece que esto podría ser un problema subjetivo, personalmente califico la eficiencia de cualquier cosa dentro del contexto completo de uso. En otras palabras, juzgo la eficiencia dependiendo de cómo se use: si no se usa en todo su potencial, lo consideraría ineficiente, pero si se usa como una “navaja suiza” que es efectiva y útil para una multitud de operaciones sin fallas (dentro de un solo entorno) entonces lo consideraría como “eficiente”. Si solo es bueno para una instancia específica, tal vez sea eficiente en su cálculo, pero la aplicación del mismo puede no serlo (es decir, no se utiliza en todo su potencial).

Dudo que esta respuesta sea suficiente debido a la ambigüedad, ¡pero gracias por el A2A de todos modos!

Answer 4

Encontrar primos gemelos es polinomial. Puede calcular dentro del tiempo polinómico si tanto n-1 como n + 1 son números primos.
Todavía es exponencialmente en función de la longitud del número.

Answer 5

Estoy de acuerdo con Mr.Jack … el algoritmo no prueba la conjetura de primos gemelos, por lo que aunque puede generar primos gemelos hasta un límite finito, puede que no funcione infinitamente. Por lo tanto, puede / no ser un algoritmo de tiempo polinómico.