Este puede ser trivial, pero me pregunto un par de cosas. Hay una manera fácil de encontrar un primo de la forma $2k+1>n$ algunos $n$?
EDITAR Cómo rápidamente podemos encontrar un primo mayor que un determinado número de $n$?
Respuestas
¿Demasiados anuncios?
Stephan Aßmus
Puntos
16
No hay ninguna prueba, pero para todos los conocidos $n \geq 20,$ hay un primer $p$ con $$ n < p < n + \log^2 n. $$ Here the logarithm is base $e \aprox 2.718281828459.$
Yo diría que la manera más rápida de encontrar un alojamiento es hacer una parte criba de Eratóstenes (ortografía??) por múltiplos de 2,3,5,7, 11 entre los límites fijados. Prueba de los sobrevivientes "probable prime" de estado. Prueba de los supervivientes para el primer certificado.
Si usted va a hacer esto de verdad, hacer el tamiz para algunos colección de pequeños números primos que se han ahorrado. Para la comparación, cuando Mathematica primer escribió sus entero de factoring, que hicieron la prueba de la división por números primos hasta 46340, estos han sido salvados en algún tipo de lista. La relevancia de la envolvente es que $$ \left\lfloor \sqrt {2^{31} -1} \right\rfloor = 46340.$$, Así que fue una buena obligado para el propósito. Si usted va a escribir sus propios comandos nextprime función, guardar una lista de números primos hasta algunos obligado, basado en gran medida en el tamaño de los números que usted está utilizando y el probable primer hueco. En algún momento, lanzando en el más pequeño de los números primos cantidades a rendimientos decrecientes, tan lejos como la velocidad de ejecución.
ver el Primer par de puntos la pendiente enfoques 1 para un montón de datos sobre el primer lagunas.
user2566092
Puntos
19546
Como se observó en otras respuestas, usted debe encontrar un primer lugar poco después de $n$ en comparación a lo grande $n$ es. Para encontrar uno como "lo más rápidamente posible," los ingredientes propuestos en otras respuestas son la clave, pero vale la pena señalar un poco de atención al detalle. Cuando se aplique primero el tamiz, entonces usted necesita para decidir cómo muchos de los primeros números primos a utilizar para su tamiz. En general, si se aplica el tamiz con base prime $p$, aproximadamente el $1/p$ de su restante de los principales candidatos serán eliminados, y la ejecución del tamiz con una base prime es mucho más rápido que una sola Rabin-Miller o las queratosis actínicas de la prueba si usted está comenzando con un rango de posibles primos de tamaño $O((\log n)^2)$. Así que como $n$ se hace más grande, usted debe ejecutar el tamiz con más base de los números primos, y, probablemente, usted desea utilizar al menos un par de cientos de base de los números primos es el típico de un gran $n$ encontrado en las grandes pruebas de primalidad. También, después de el tamiz, al ejecutar Rabin-Miller para posibles pruebas de primalidad (que es mucho más rápido por iteración de la garantía de pruebas de primalidad AKS), si usted quiere tener un total de algoritmo, que es casi siempre tan rápido como sea posible, entonces usted desee ejecutar las queratosis actínicas una vez y casi se garantiza que la respuesta va a ser "prime", de modo que se desea ejecutar Rabin-Miller para un decente número de iteraciones (como al menos 10) en un candidato número primo, mientras que la prueba todavía dice "probablemente el primer" y, a continuación, sólo habrá un $1/4^{10} = $ aproximadamente uno en un millón de probabilidad de que el número no es primo si pasa estos 10 Rabin-Miller iteraciones, por lo que es casi seguro que el número es primo, en cuyo caso sólo tiene que ejecutar la lentitud de primalidad AKS la comprobación de una vez para conseguir su primer. También tenga en cuenta que no tiene sentido para ejecutar Rabin-Miller iteraciones en el round robin de la moda en todo el conjunto de números que usted está considerando como candidato de los números primos después de la criba; puede ser más eficiente a prueba de candidato número uno-por-uno con Rabin-Miller, la repetición de Rabin-Miller iteraciones en el mismo número o bien hasta obtener una iteración que dice "no primos" o 10 iteraciones en una fila que decir "probablemente primo". Si un número no es primo, el número promedio de Rabin-Miller iteraciones se tiene que ejecutar para determinar este valor es inferior a 2.
