Desafío
En esta tarea, se le daría un número entero N, debe generar el primo más cercano al número entero.
Si el número es primo, genera el número.
La entrada N se da en una sola línea, las entradas son terminadas por EOF. El número de entradas no excedería los 10000 valores.
El desafío es implementar la solución más rápida para que pueda procesar un máximo de 10000 valores lo más rápido posible.
Entrada
299246598
211571591
71266182
645367642
924278231
Salida
299246587
211571573
71266183
645367673
924278233
Restricciones
- N es menor que 2 ^ 64
- Cuide sus dedos, no use más de 4096 bytes en su solución.
- Puede usar cualquier idioma de su elección siempre y cuando no lo esté usando, es algo incorporado para los números primos.
- ¡La solución más rápida, con la complejidad de tiempo más eficiente gana!
ADICIONAL:
Esta es una versión más fácil del mismo problema (con N <2 ^ 31) para que pueda intentar verificar su enfoque en casos más pequeños antes de construirlo para este problema real.
code-challenge
primes
fastest-algorithm
Quijotesco
fuente
fuente
Respuestas:
Pitón
fuente
PARI GP
fuente
NextPrime[n]
funciona estrictamente por encima den
3 condiciones ...Haskell
Debería ser bastante rápido. Requiere el paquete
primes
, disponible desde hackage.fuente
Rubí
fuente
Java
Esto lleva <1 segundo hasta que num comienza a ser mayor que 10 ^ 8. No es lo suficientemente eficiente, considerando que 2 ^ 64 es aproximadamente 1.8 * 10 ^ 19. (Comenzó hace 10 ^ 15 hace 6 minutos y todavía está ejecutando D :)
Esto da una respuesta segura cada vez, ya que no usa un algoritmo probabilístico, pero paga mucho por eso en términos de eficiencia: 10 ^ 18 tendría más de 5 millones de números primos en la lista, e incluso más antes del tamizado. Puede mejorar esto en algún momento con un mejor algoritmo de tamizado. No espero que esto supere a ninguno de los otros :)
fuente
Haskell
Esto es bastante rápido y no determinista hasta un límite grande. También mi primer Haskell :).
wc
dice 903b sin compilar.Editar: si alguien quiere estimar la complejidad del tiempo, sé mi invitado ...
fuente