Desafio de código: o primo mais próximo

8

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.

Quixotesco
fonte
2
O cálculo básico que você solicitou foi uma sub-parte de codegolf.stackexchange.com/q/1977/78 , apenas alguns dias atrás. Pessoalmente (ou seja, sem usar meu chapéu de moderador), acho essa repetição entediante.
dmckee --- ex-moderador gatinho
Podemos usar testes probabilísticos de primalidade?
Keith Randall
2
Como você planeja julgar mais rápido? Por velocidade de execução em hardware fixo? Ou analisando a complexidade dos envios? De alguma forma, você normalizará o custo das operações em diferentes idiomas? - Por fim, esse desafio parece muito simples. Realmente não há espaço para inovar aqui.
MtnViewMark
1
@gnibbler: Usando uma tabela de pesquisa de todos os 2 ^ 64 valores lhe dará a solução mais rápida sse você pode espremer toda a coisa (solução) através do 4096 bytes janela :-)
Quixotic
2
@Debanjan, podemos assumir a hipótese generalizada de Riemann ao afirmar a complexidade do tempo?
Peter Taylor

Respostas:

6

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
Keith Randall
fonte
Penso que deve-se notar que o teste de primalidade de Miller-Rabin não é incondicionalmente determinístico. 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
fonte
Suponho mathematica seria algo semelhante, mas ele é NextPrime[n]trabalha estritamente acima nassim 3 condições ....
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

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

FUZxxl
fonte
Desculpe, isso não é permitido, este é um desafio de código e acho que isso também não deve funcionar na versão mais curta do problema.
Quixotic
Como você disse, importar código é uma pena. A menos que você julgar os outros por um outro padrão que o seu próprio
Dr. belisarius
@belisarius Você erra. Como não é um código de golfe, o tamanho do código não é uma opção. A tarefa que você tentou resolver foi o código de golfe.
FUZxxl
1
Usar números primos embutidos não é uma boa escolha, pois isso não é um codegolf e o ponto principal é implementar uma abordagem rápida. Esta resposta merece um -1, claramente. Eu não me sinto de mau humor, no entanto.
Dr. belisarius
@belisarius Se você tiver necessidade de qualquer tipo de "vingança", apenas me vote. Não há problema com isso; no entanto, isso é estilo ruim.
FUZxxl
0

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
}
st0le
fonte
Usar números primos embutidos não é uma boa escolha, pois não é um codegolf e o ponto principal é implementar uma abordagem rápida; a decisão da melhor pontuação deve ser baseada na complexidade da solução, de modo que isso não seja permitido, desculpe.
Quixotic
0

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

Transformada de Fourier de Rin
fonte
0

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
alexander-brett
fonte