Code-Challenge: The Prime más cercano

8

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.

Quijotesco
fuente
2
El cálculo básico que solicitó fue una subparte de codegolf.stackexchange.com/q/1977/78 , hace solo un par de días. Personalmente (es decir, sin usar el sombrero de moderador), encuentro aburrida esa repetición.
dmckee --- ex-gatito moderador
¿Podemos usar pruebas de primalidad probabilística?
Keith Randall el
2
¿Cómo planeas juzgar más rápido? ¿Por velocidad de ejecución en hardware fijo? ¿O analizando la complejidad de las presentaciones? ¿Normalizará de alguna manera el costo de las operaciones en diferentes idiomas? - Por último, este desafío parece demasiado simple. Realmente no hay espacio para innovar aquí.
MtnViewMark
1
@gnibbler: el uso de una tabla de búsqueda de todos los valores 2 ^ 64 le dará la solución más rápida si puede exprimir todo (la solución) a través de la ventana de 4096 bytes :-)
Quixotic
2
@Debanjan, ¿podemos asumir la hipótesis generalizada de Riemann al indicar la complejidad del tiempo?
Peter Taylor

Respuestas:

6

Pitón

import sys,random

# Miller-Rabin primality test, error rate 2^-200.                                                                                                                           
def prime(N):
  if N<3:return N==2
  s=0
  d=N-1
  while (d&1)==0:s+=1;d>>=1
  for i in xrange(100):
    a=random.randrange(1,N)
    if pow(a,d,N)!=1 and all(pow(a,d<<r,N)!=N-1 for r in xrange(s)):return 0
  return 1

for N in map(int,sys.stdin):
  d=0
  while 1:
    if prime(N+d):print N+d;break
    if prime(N-d):print N-d;break
    d+=1
Keith Randall
fuente
Creo que debe tenerse en cuenta que la prueba de primalidad de Miller-Rabin no es incondicionalmente determinista. en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
mbomb007
2

PARI GP

a(n)=x=[precprime(n),nextprime(n)];print(if(x[1]-n<n-x[2],x[1],x[2]))
while(1,print(a(input())))
st0le
fuente
Supongo que Mathica sería algo similar, pero NextPrime[n]funciona estrictamente por encima de n3 condiciones ...
st0le
0

Haskell

import Data.Numbers.Primes

-- Assuming, we are on x64
nearestPrime :: Int -> Int
nearestPrime n | n - s < l - n = s
               | otherwise     = l where
  l = head $ dropWhile (not . isPrime) [n..]
  s = head $ dropWhile (not . isPrime) [n,n-1..]

main = readLine >>= print . nearestPrime . read

Debería ser bastante rápido. Requiere el paquete primes, disponible desde hackage.

FUZxxl
fuente
Lo sentimos, eso no está permitido, este es un desafío de código y supongo que esto tampoco debería funcionar en la versión más corta del problema.
Quijotesco
Como dijiste, importar código es una pena. A menos que juzgue a los demás por otro estándar que no sea el suyo
Dr. belisarius
@belisarius Te equivocas. Este no es un código de golf, por lo que el tamaño del código no es una opción. Sin embargo, la tarea que intentó resolver fue el golf de código.
FUZxxl
1
El uso de primos incorporados no es una buena opción, ya que no se trata de codegolf y el objetivo es implementar un enfoque rápido. Esta respuesta merece un -1, claramente. Sin embargo, no me siento de mal humor.
Dr. belisarius
@belisarius Si tiene la necesidad de algún tipo de "venganza", simplemente búsqueme. No hay problema con eso; sin embargo, ese es un mal estilo.
FUZxxl
0

Rubí

require 'prime'
gets(p).split.each{|n|
    a=b=n.to_i
    a,b = a-1,b+1 while !a.prime?  and !b.prime?
    p a.prime? ? a : b
}
st0le
fuente
Usar primos incorporados no es una buena opción, ya que no se trata de codegolf y el objetivo es implementar un enfoque rápido, la decisión de la mejor puntuación se basará en la complejidad de la solución, por lo que no está permitido, lo siento.
Quijotesco
0

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 :)

import java.util.*;

class ClosestPrime {

    public static double closest(double num) {
        double returnme = 0;
        if (isPrime(num)){returnme = num;}
        for (double i = 0; i < num / 2; i++) { //checks each side of num
            if (isPrime(num - i)) {returnme = num - i;
                break;}
            if (isPrime(num + i)) {returnme = num + i;
                break;}
        }
        return returnme;
    }

    private static boolean isPrime(double num) {
        long sqrtnum = (long) Math.sqrt(num); //no need to check for factors above sqrt(num)
        List<Double> primes = new LinkedList<Double>();
        primes.add((double) 2);
        for (double i = 3; i < sqrtnum; i+=2) {primes.add(i);} //fill list with odd numbers

        for (long i = 2; i <= sqrtnum; i++) {
            if (num / i % 1 == 0) {return false;}   
            ListIterator<Double> iter = primes.listIterator();
            while (iter.hasNext()) {if ((iter.next()) / i % 1 == 0){iter.remove();}} //sieving by Eratosthenes
        }
        return true;
    }
}

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 :)

Transformada de Fourier de Rin
fuente
0

Haskell

Esto es bastante rápido y no determinista hasta un límite grande. También mi primer Haskell :). wcdice 903b sin compilar.

Editar: si alguien quiere estimar la complejidad del tiempo, sé mi invitado ...

import System.Environment
import Math.NumberTheory.Moduli -- arithmoi
import Data.List.Ordered -- data-ordlist

main :: IO ()
main = interact processInputStrings

processInputStrings :: String -> String
processInputStrings input = unlines $ map show $ getClosestMembers $ map read $ lines $ input 

isPrime :: Integer -> Bool
{- Implement the Miller–Rabin test with basis valid up to somewhere > 2^64 -}
isPrime 2 = True
isPrime 3 = True
isPrime t =  let
        factor :: (Integer, Integer) -> (Integer, Integer)
        factor (d,s) = if even d then factor (d `div` 2, s+1) else (d,s)
        (d,s) = factor (t-1, 0)
    in 
        and $ map (\a ->
            or [(powerMod a d t) == 1, or [(powerMod a (2^r * d) t) == t-1 | r <- [0..s-1]]]
        ) $ filter (<t) [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]


getClosestMembers :: [Integer] -> [Integer]
getClosestMembers inputs = map (\i -> head [n | n <- concat [[i-d, i+d] | d <- [0..]], isPrime n]) inputs
alexander-brett
fuente