Al menos el primer mayor de 2000

Question

Soy un poco curioso en cuanto a cómo "real" de los matemáticos a resolver este problema.

"Encontrar el menor número primo mayor que 2000."

Por supuesto, siempre se puede ir a la fuerza bruta:

IF N IS PRIME, OUTPUT N
ELSE INCREASE N BY 1

Pero eso no es divertido. (Especialmente cuando el número es muy alto.)

Existen algoritmos/trucos/etc. que me puede ayudar a resolver esto rápidamente y de manera eficiente, sobre todo si me dieron valores grandes de N?

Answer 1

Espero que existen herramientas más potentes disponibles; pero para un simple enfoque que se aplicará el Teorema de los números Primos (PNT) y de un tamiz (como Yuval ya ha sugerido).

Una consecuencia útil de la PNT es que alrededor de un número N, aproximadamente uno de cada log(N) números es primo. (Por 'registro, el número de los teóricos siempre quiere decir que el logaritmo natural 'ln'.) Así, alrededor del año 2000, aproximadamente 1 de cada 7.6 números es primo. Vamos a buscar entre los números de 2001 hasta el 2060 para nuestro próximo primer ... estoy dejando un espacio extra en caso de que un gran primer hueco que sucede a mostrar hasta alrededor del año 2000.

Ahora vamos a utilizar el tamiz-- podemos tirar todos los números pares en nuestra lista, ya que ciertamente no son números primos. A continuación, podemos tirar todo lo divisible por 3, entonces todo divisible por 5, 7, 11,... Cuando debemos dejar de cribado? Podemos parar cuando llegamos a $\sqrt{2060} \approx 45$, ya que si cualquier número en nuestra lista, puede ser factorizado como M = ab, entonces uno de los factores debe ser menor o igual a la raíz cuadrada del número más grande en nuestra lista.

Por supuesto, un equipo que estaría feliz de hacer este proceso para usted. Pero, acabo de escribir hacia abajo en la lista y fue a través de mi fondo de tamiz (los números primos hasta un 43); y tengo los números primos 2003, 2011, 2017, 2027, 2029, 2039, 2053.

Answer 2

Tamizado, por sí solo, es un mal planteamiento del problema a menos que n es pequeño (que, en tu ejemplo, es). Un mejor enfoque para los grandes números: elija un intervalo apropiado,* colador pequeño de los números primos, la prueba de los números restantes con un probable-primer examen, entonces (si se desea) demostrar primalidad con ECPP o un algoritmo similar (para los pequeños primos, ABR-CL es mejor).

Muchos programas que pueden hacer esto de búsqueda para usted, a pesar de que generalmente se omite el último paso (Pari y Mathematica, al menos).

.* Si el intervalo es elegido al azar, la longitud de 4.5 log x es 95% probable que mantenga al menos un primo, ya $4.5e^{-4.5}\approx0.05$. Si el intervalo es adversarially elegido tener unos primos, usted puede elegir un intervalo tan largo como acerca de $2e^{-\gamma}\log^2x$. Si el rendimiento es crítico que usted puede determinar el óptimo de cribado basado en la distancia en el tiempo y otros recursos tomados por ambas partes.

Answer 3

Si usted quiere encontrar varios de los números primos a la vez a partir de un cierto punto, usted puede utilizar un colador.

Answer 4

Todos los números primos, a excepción de$2$$3$, son de la forma $6n\pm1$. Ahora, ¿cuál es el múltiplo más cercano de $6$$2000$? No puede ser $2000$ sí, ya que, a pesar de ser incluso, la suma de sus dígitos no es un múltiplo de a $3$. Lo mismo vale para los $2002$. A continuación, $2004$ es la respuesta. Vamos a ver $2004-1=2003$. De hecho, es el primer.

Answer 5

Un entero $p$ es primo si y sólo si la siguiente ecuación se tiene: \begin{eqnarray} \sum_{n \geq 1} \left \lfloor \frac{p}{n} \right \rfloor - \left \lfloor \frac{p-1}{n} \right \rfloor = 2 \end{eqnarray} NB: El infinito número de términos de la suma está ahí para dar cabida arbitrariamente un gran número entero $p$, pero la suma eventualmente produce una cadena de $0$s. (Ver Crandall y Pomerance, Números Primos: Una Perspectiva Computacional, Nueva York: Springer, ISBN 0-387-04777-9)

Después de observar que los $2001$ $2002$ ambos violan la prueba de pronto, pero $2003$ no lo hace, entonces usted puede utilizar cualquier número de pruebas de primalidad (o elegir para demostrar que la suma es igual a 2 para establecer la primalidad directamente). De lo contrario, usted puede intentar algo como Wilson del teorema que establece que: Un número entero $p$ es primo si y sólo si $(p-1)! \equiv -1 \mod p$.

Mathematica da el resultado correcto en menos de 1 segundo: $2003$ es el primer prime mayor que $2000$.