Desafio

Nesta tarefa, você receberia um número inteiro N, que deverá gerar o primo mais próximo do número inteiro.

Se o número for primo, imprima o número.

A entrada N é fornecida em uma única linha, as entradas são terminadas por EOF. O número de entradas não excederia 10000 valores.

O desafio é implementar a solução mais rápida para que ele possa processar no máximo 10.000 valores o mais rápido possível.

Entrada

 299246598
 211571591
 71266182
 645367642
 924278231

Resultado

 299246587
 211571573
 71266183
 645367673
 924278233

Restrições

• N é menor que 2 ^ 64
• Cuidado com os dedos, não use mais de 4096 bytes na sua solução.
• Você pode usar qualquer idioma de sua escolha, desde que não o utilize, para os primos.
• Solução mais rápida, com a complexidade de tempo mais eficiente ganha!

ADICIONADO:

Esta é uma versão mais fácil do mesmo problema (com N <2 ^ 31), para que você possa tentar verificar sua abordagem em casos menores antes de construí-la para esse problema real.

Pitão

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

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

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

Deve ser bem rápido. Requer o pacote primes, disponível no hackage.

Rubi

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
}

Java

Isso leva <1 segundo até que num comece a ser maior que 10 ^ 8. Não é eficiente o suficiente, considerando que 2 ^ 64 é de cerca de 1,8 * 10 ^ 19. (Iniciou 10 ^ 15 há 6 minutos e ainda está executando o 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;
    }
}

Isso sempre dá uma resposta certa, já que não usa um algoritmo probabilístico, mas paga muito por isso em termos de eficiência - 10 ^ 18 teria mais de 5 milhões de números primos na lista e ainda mais antes da peneiração. Pode melhorar isso em algum momento com um algoritmo de peneira melhor. Não espero que isso supere nenhum dos outros :)

Haskell

Isso é muito rápido e não determinístico até um grande limite. Também o meu primeiro Haskell :).wcdiz 903b descompilado.

Edit: Se alguém quiser estimar a complexidade do tempo, seja meu convidado ...

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