Introdução:

Você acidentalmente corrompeu o fluxo do tempo com um dispositivo criado por diversão, que acabou sendo uma máquina do tempo. Como resultado, você foi empurrado para o futuro distante. Você percebeu que a computação, o poder de processamento e os computadores em geral evoluíram em uma quantidade enorme, uma quantidade infinita para ser preciso . Então você pega um computador com memória infinita e poder de processamento. Você não tem idéia de como ele pode ter memória infinita e poder de processamento infinito, mas apenas aceita e volta ao presente.

Desafio:

Você ouviu dizer que a pessoa que descobriu o maior prime atualmente 2^74,207,281 − 1recebeu US $ 100.000. Você decide criar um programa que encontre o próximo número primo, pois deseja recuperar o dinheiro gasto no computador. Você faz um que recebe a entrada de um número e encontra o próximo número primo, por força bruta ou por qualquer outro método.

Esclarecimentos: Você tem uma máquina hipotética com memória infinita e poder de processamento. Seu programa NÃO DEVE ser limitado (por exemplo: int's de C # podem armazenar de -2,147,483,648até 2,147,483,647), bem, seu programa deve ser capaz de armazenar e trabalhar com qualquer número de qualquer tamanho. Você tem recursos infinitos; portanto, você não deveria se importar se ficaria sem memória se permitisse isso.

Exemplo de E / S:
Entrada: o maior primo descoberto atualmente com 22.338.618 dígitos.
Saída: exatamente o próximo prime

Obviamente, você não precisa provar que funciona, pois levaria muito tempo para computar em uma máquina física. Mas se você moveu seu programa para uma máquina hipotética com poder / memória de processamento infinito, ele deve calcular instantaneamente.

Encontrar o próximo primo e verificar se um número é primo, são duas coisas completamente diferentes

Mathematica, 9 bytes

NextPrime

Python 3 , 45 bytes

f=lambda n,k=1,m=1:m%k*k>n or-~f(n,k+1,m*k*k)

Experimente online!

Python 2, 78 77 76 74 bytes

def f(n):
 while 1:
    n+=1
    if[i for i in range(1,n)if n%i<1]==[1]:return n

-1 byte graças a @KritixiLithos
-1 byte graças a @FlipTack
-2 bytes graças a @ElPedro

Gelatina , 2 bytes

Æn

Experimente online!

This implicitly takes input z and, according to the manual, generate the closest prime strictly greater than z.

Oasis, 2 bytes

Run with the -n flag.

Code:

p

Try it online!

Bash + coreutils, 52 bytes

for((n=$1,n++;`factor $n|wc -w`-2;n++)){ :;};echo $n

Try it online!

The documentation for bash and factor do not specify a maximum integer value they can handle (although, in practice, each implementation does have a maximum integer value). Presumably, in the GNU of the future on your infinitely large machines, bash and factor will have unlimited size integers.

Maxima, 10 bytes

next_prime

A function returns the smallest prime bigger than its argument.

Brachylog, 2 bytes

<ṗ

Try it online!

Explanation

(?) <   (.)      Input < Output
      ṗ (.)      Output is prime
                 (Implicit labelization of the Output at the end of the predicate)

Python with sympy, 28 bytes

import sympy
sympy.nextprime

sympy.nextprime is a function which does what it says on the tin. Works for all floats.

repl.it

Python, 66 59 bytes

-4 bytes thanks to Lynn (use -~)
-3 bytes thanks to FlipTack (use and and or, allowing ...==1 to be switched to a ...-1 condition.)

f=lambda n:sum(-~n%-~i<1for i in range(n))-1and f(n+1)or-~n

repl.it

A recursive function that counts up from n until a prime is found by testing that only one number exists up to n-1 that divides it (i.e. 1). Works for all integers, raises an error for floats.

Works on 2.7.8 and 3.5.2, does not work on 3.3.3 (syntax error due to lack of space between ==1 and else)

Python, 114 83 bytes

def g(b):
 while 1:
  b+=1
  for i in range(2,b):
   if b%i<1:break
  else:return b

Without builtins, if there are any.

-30 by removing whitespace and -1 by changing b%i==0 to b%i<1

Perl 6, 25 bytes

{first *.is-prime,$_^..*}

How it works

{                       }  # A lambda.
                  $_ ..*   # Range from the lambda argument to infinity,
                    ^      # not including the start point.
 first           ,         # Iterate the range and return the first number which
       *.is-prime          # is prime.

Perl 6, 32 bytes

{first {all $_ X%2..^$_},$_^..*}

With inefficient custom primality testing.

How it works

Outer structure is the same as above, but the predicate passed to first (to decide if a given number is prime), is now:

{               }  # A lambda.
     $_            # Lambda argument (number to be tested).
          2..^$_   # Range from 2 to the argument, excluding the end-point.
        X          # Cartesian product of the two,
         %         # with the modulo operator applied to each pair.
 all               # Return True if all the modulo results are truthy (i.e. non-0).

Pyke, 8 7 bytes

~p#Q>)h

Try it here!

4 bytes, noncompeting

(Interpreter updated since challenge posted)

~p<h

Try it here!

~p   -   primes_iterator()
  <  -  filter(^, input() < i)
   h - ^[0]

J, 4 bytes

4&p:

Simples embutido para o próximo prime.

05AB1E , 16 13 bytes (Emigna @ -3 bytes)

2•7£?ÿ•o[>Dp#

Experimente online!

2•7£?ÿ•o        # Push current largest prime.
        [   #    # Until true..
         >Dp    # Increment by 1, store, check primality.
                # After infinite loop, implicitly return next prime.

Perl, 30 bytes (29 +1 para -p):

(1x++$_)=~/^(11+?)\1+$/&&redo

Uso

Digite o número depois de pressionar return (entrada 12345 no exemplo abaixo, saídas 12347):

$ perl -pe '(1x++$_)=~/^(11+?)\1+$/&&redo'
12345
12347

Como funciona

• Defina uma sequência de 1's que tem comprimento ++$_, onde $_é inicialmente o valor de entrada
• O regex verifica se a sequência de 1s é de comprimento não primário (explicado aqui ).
• Se o comprimento da string não for primo, a verificação será reavaliada para o próximo número inteiro (++$_ )
• Se o comprimento da string for primo, o whileloop implícito sai e -pimprime o valor de$_
• Nota: não há necessidade de lidar com a aresta "1"de comprimento 1, pois nunca será usada para valores menores que 1, de acordo com a especificação.

Java 7, 373 343 334 303 268 bytes

import java.math.*;class M{public static void main(String[]a){BigInteger n,i,o,r=new BigInteger(a[0]);for(r=r.add(o=r.ONE);;r=r.add(o)){for(n=r,i=o.add(o);i.compareTo(n)<0;n=n.mod(i).compareTo(o)<0?r.ZERO:n,i=i.add(o));if(n.compareTo(o)>0)break;}System.out.print(r);}}

-75 bytes obrigado @Poke

Ungolfed:

import java.math.*;
class M{
  public static void main(String[] a){
    BigInteger n,
               i,
               o,
               r = new BigInteger(a[0]);
    for(r = r.add(o = r.ONE); ; r = r.add(o)){
      for(n = r, i = o.add(o); i.compareTo(n) < 0; n = n.mod(i).compareTo(o)< 0
                                                        ? r.ZERO
                                                        : n,
                                                   i = i.add(o));
      if(n.compareTo(o) > 0){
        break;
      }
    }
    System.out.print(r);
  }
}

Experimente aqui.

Alguns exemplos de entradas / saídas:

7 -> 11
1609 -> 1613
104723 -> 104729

QBIC , 34 bytes

:{a=a+1[2,a/2|~a%b=0|b=a]]~a<b|_Xa

Baseado neste testador de primalidade QBIC . Explicação:

:{a=a+1    Read 'a' from the command line, start an infinite loop 
           and at the start of each iteration increment 'a'
[2,a/2|    FOR b = 2, b <= a/2, b++
~a%b=0|    IF b cleanly divides a, we're no prime
b=a]]      so, break out of the FOR loop ( ]] = End if, NEXT )
~a<b|      If the FOR loop completed without breaking
_Xa        then quit, printing the currently tested (prime) number
           The second IF and the DO-loop are implicitly closed by QBIC.

JavaScript (ES7), 61 bytes

a=>{for(;a++;){for(c=0,b=2;b<a;b++)a%b||c++;if(!c)return a;}}

Uso

f=a=>{for(;a++;){for(c=0,b=2;b<a;b++)a%b||c++;if(!c)return a;}}
f(2)

Resultado

3

MATL, 3 bytes

_Yq 

A função Yqretorna o próximo primo do valor absoluto da entrada, se a entrada for negativa, de modo que agarramos implicitamente a entrada, a negamos ( _) e localizamos o próximo primo usando Yq.

Experimente Online!

Haskell, 42 46 43 bytes

f n=[i|i<-[n..],all((>0).rem i)[2..i-1]]!!1

o código usual para força bruta.

Claro que isso encontra o próximo menor número primo depoisn . Não há maior prime.

Funciona para n > 0 .

editar: Assume que né primo. Obrigado ao conselho de @Laikoni nos comentários .

SimpleTemplate, 132 bytes

O algoritmo é terrível, pois tenho que fazer meu próprio código para verificar se um número é primo ou não.
Provou ser horrível, mas funciona.

{@setY argv.0}{@setX 1}{@whileX}{@setX}{@set+T Y,-1}{@for_ from2 toT}{@ifY is multiple_}{@incX}{@/}{@/}{@ifX}{@incY}{@/}{@/}{@echoY}

Recebe o número como o primeiro argumento, produzindo o resultado.

Ungolfed:

{@set number argv.0}
{@set remainder 1}
{@while remainder}
    {@set remainder 0}
    {@set+ tmp number, -1}
    {@for divisor from 2 to tmp}
        {@if number is multiple divisor}
            {@inc by 1 remainder}
        {@/}
    {@/}
    {@if remainder}
        {@inc by 1 number}
    {@/}
{@/}
{@echo number}

Alguma dica de como remover isso por último @if?

Lua, 876 bytes

function I(a)a.s=a.s:gsub("(%d)(9*)$",function(n,k)return tostring(tonumber(n)+1)..("0"):rep(#k)end)end function D(a)a.s=a.s:gsub("(%d)(0*)$",function(n,k)return tostring(tonumber(n)-1)..("9"):rep(#k)end):gsub("^0+(%d)","%1")end function m(a,b)local A=K(a)local B=K(b)while V(0,B)do D(A)D(B)end return A end function M(a,b)local A=K(a)local B=K(b)while V(m(B,1),A)do A=m(A,B)end return A end function l(n)return#n.s end function p(a)local A=K(a)local i=K(2)while V(i,A)do if V(M(A,i),1)then return false end I(i)end return true end function V(b,a)A=K(a)B=K(b)if l(A)>l(B)then return true end if l(B)>l(A)then return false end for i=1,l(A)do c=A.s:sub(i,i)j=B.s:sub(i,i)if c>j then return true elseif c<j then return false end end return false end function K(n)if(type(n)=='table')then return{s=n.s}end return{s=tostring(n)}end P=K(io.read("*n"))repeat I(P)until p(P)print(P.s)

Lua, diferentemente de outros idiomas, possui um Tamanho Máximo Inteiro. Quando um número fica maior que 2 ³² , as coisas param de funcionar corretamente e Lua começa a tentar fazer estimativas em vez de valores exatos.

Como tal, eu tive que implementar um novo método de armazenamento de números, em particular, eu os armazenei como seqüências de caracteres Base10, porque Lua não tem um limite de tamanho em Strings, além do tamanho da memória.

Eu sinto que essa resposta é muito mais importante para o espírito da pergunta, pois ela mesma deve implementar números inteiros de precisão arbitrários, além de um teste primo.

Explicado

-- String Math
_num = {}

_num.__index = _num

-- Increase a by one.
-- This works by grabbing ([0-9])999...$ from the string.
-- Then, increases the first digit in that match, and changes all the nines to zero.
-- "13", only the "3" is matched, and it increases to 1.
-- "19", firstly the 1 is turned to a 2, and then the 9 is changed to a 0.
-- "9" however, the 9 is the last digit matched, so it changes to "10"
function _num.inc(a)
    a.str = a.str:gsub("(%d)(9*)$",function(num,nines)
            return tostring(tonumber(num)+1)..("0"):rep(#nines)
        end)
end


-- Decrease a by one
-- Much like inc, however, uses ([0-9])0...$ instead.
-- Decrements ([0-9]) by one and sets 0... to 9...
-- "13" only the "3" is matched, and it decreases by one.
-- "10", the "1" is matched by the ([0-9]), and the 0 is matched by the 0..., which gives 09, which is clipped to 9.
function _num.dec(a)
    a.str = a.str:gsub("(%d)(0*)$",function(num,zeros)
        return tostring(tonumber(num)-1)..("9"):rep(#zeros)
    end)         :gsub("^0+(%d)","%1")
end

-- Adds a and b
-- Makes A and B, so that the original values aren't modified.
-- B is then decremented until it hits 0, and A is incremented.
-- A is then returned.
function _num.__add(a,b)
    local A = str_num(a)
    local B = str_num(b)
    while B > 0 do
        A:inc()
        B:dec()
    end
    return A
end

-- Subs b from a
-- Works just like Addition, yet Dec's A instead of Incs.
function _num.__sub(a,b)
    local A = str_num(a)
    local B = str_num(b)
    while B > 0 do
        A:dec()
        B:dec()
    end
    return A
end

-- A % B
-- Makes A and B from a and b
-- Constantly subtracts B from A until A is less than B
function _num.__mod(a,b)
    local A = str_num(a)
    local B = str_num(b)
    while A >= B do
        A = A - B
    end
    return A
end

-- #a
-- Useful for golfiness
function _num.__len(n)
    return #n.str
end

-- Primacy Testing
-- Generates A from a and i from 2.
-- Whilst i is less than A, i is incremented by one, and if A % i == 0, then it's not a prime, and we return false.
-- Once that finishes, we return true.
function _num.isprime(a)
    local A = str_num(a)
    local i = str_num(2)
    while i < A do
        if A%i < 1 then
            return false
        end
        i:inc()
    end
    return true
end

-- b < a
-- A and B are generated from a and b
-- Fristly, if the length of A and B aren't equal, then that result is output.
-- Otherwise, each character is searched from left to right, the moment they are unequal, the difference is output.
-- If all the characters match, then it's equal. Return false.
function _num.__lt(b,a)
    A=str_num(a)
    B=str_num(b)
    if #A > #B then
        return true
    end
    if #B > #A then
        return false
    end
    for i=1, #A.str do
        As = A.str:sub(i,i)
        Bs = B.str:sub(i,i)
        if As > Bs then
            return true
        elseif As < Bs then
            return false
        end
    end
    return false
end


-- b <= a
-- Same as b < a, but returns true on equality.
function _num.__le(b,a)
    A=str_num(a)
    B=str_num(b)
    if #A > #B then
        return true
    end
    if #B > #A then
        return false
    end
    for i=1, #A.str do
        As = A.str:sub(i,i)
        Bs = B.str:sub(i,i)
        if As > Bs then
            return true
        elseif As < Bs then
            return false
        end
    end
    return true
end

-- Just straight up returns it's string component. Endlessly faster than the int equivalent, mostly because it never is anything _but_ the string form.
function _num.__tostring(a)
    return a.str
end

-- Just set up the metatable...
function str_num(n)
    if(type(n)=='table')then
        return setmetatable({str = n.str}, _num)
    end
    return setmetatable({str = tostring(n)}, _num)
end

-- Generate a new str_num from STDIN
Prime = str_num(io.read("*n"))

-- This is handy, because it will call Prime:inc() atleast once, and stop at the next prime number it finds.
-- Basically, if it weren't for all that overhead of making the math possible, that's all this would be.
repeat
    Prime:inc()
until Prime:isprime()
print(Prime)

Embora o acima mencionado use Metatables, em vez de apenas funções regulares, como a resposta real, que resultou menor.

Ruby, 28 + 6 = 34 bytes

Usa a -rprimebandeira.

f=->i{i+=1;i.prime??i :f[i]}

Versão não recursiva para 31 + 6 = 37 bytes:

->i{i+=1;i+=1 while i.prime?;i}

Python + primefac , 34 32 bytes

Não é tão curto quanto usar sympy(outra resposta já o usa), mas ainda é muito curto e é muito mais rápido.

import primefac as p
p.nextprime

Experimente online

Entrada de 2**2000conclui em alguns segundos.

Japonês, 6 bytes

_j}aUÄ

Execute-o online.