La determinación de la próxima Doble Prime?

Question

Un simple realmente me pregunta, supongo. Existe un algoritmo o método que dado un entero $N$ hay una manera para determinar la siguiente twin primer par mayor que $N$?

Si sí, entonces usted podría por favor explicar?

Answer 1

No es ni siquiera sabe que siempre hay un doble primer par mayor que $N$ (estrictamente hablando, no hay un algoritmo que se sabe que funciona).

Answer 2

Deje $x=N+1$. Si $x$ $x+2$ es de los primeros, ya está hecho. Si no, vamos a $x=x+1$ y repetir. :-P

Answer 3

Nope. Que yo sepa no hay ningún algoritmo más allá de sieveing de los números primos pasado $N$ hasta encontrar un par de gemelas.

Answer 4

Yo no estaría tan rápido para descartar timidpueo del "algoritmo" (a pesar de que fácilmente podría ser más rápidas mediante la sustitución de $N+1$$N+6$, entre otros trucos). Conjecturally, el espaciamiento promedio entre los dos números primos es $O(\log^2 N)$ y el peor de los casos la separación se $O(\log^3 N)$. Así, en la práctica, esto es un polinomio de tiempo "algoritmo" (aunque no está garantizado para terminar, de ahí las comillas).

Answer 5

Hay un superfast método: No busque primos! Busque una pequeña clase de semiprimes. El producto de todas las camas de los números primos es un perfecto cuadrado menos 1. Y ya que estamos buscando semiprimes, una prueba de primalidad no es necesario. Cualquier factor (prime o no) menor que la raíz cuadrada de X^2 - 1 elimina el compuesto como un candidato. Además, estos factores son generalmente trivial, es decir, que se encuentran mucho antes de X.

Demostración: http://www.naturalnumbers.org/TwinPrimeCalc.xlsm