Introducción:

Accidentalmente corrompiste el flujo del tiempo con un dispositivo que hiciste por diversión, que resultó ser una máquina del tiempo. Como resultado, te empujaron al futuro lejano. Te diste cuenta de que la informática, la potencia de procesamiento y las computadoras en general han evolucionado en gran medida, una cantidad infinita para ser precisos . Entonces, se toma una computadora con memoria infinita y potencia de procesamiento. No tienes idea de cómo puede tener memoria infinita y poder de procesamiento infinito, pero simplemente lo aceptas y regresas al presente.

Desafío:

Escuchaste que la persona que descubrió la prima más grande en la actualidad 2^74,207,281 − 1recibió $ 100,000. Decide hacer un programa que encuentre la próxima prima, ya que desea recuperar el dinero que gastó en la computadora. Haces uno que toma la entrada de un número y encuentra el siguiente número primo, ya sea por fuerza bruta o por cualquier otro método.

Aclaraciones: tiene una máquina hipotética con memoria infinita y potencia de procesamiento. Su programa NO DEBE estar limitado (por ejemplo: los int. De C # pueden almacenar de -2,147,483,648a 2,147,483,647), bueno, su programa debe poder almacenar y trabajar con cualquier número de cualquier tamaño. Tiene recursos infinitos, por lo que no debería importarle si se quedaría sin memoria si lo permitiera.

Ejemplo de E / S:
Entrada: El primo descubierto más grande actualmente con 22,338,618 dígitos.
Salida: exactamente la próxima prima

Obviamente, no tiene que demostrar que funciona, ya que tomaría mucho tiempo calcularlo en una máquina física. Pero si movió su programa a una máquina hipotética con capacidad / memoria de procesamiento infinito, debería computar al instante.

Encontrar el próximo primo y verificar si un número es primo son dos cosas 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)

Pruébalo en línea!

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 gracias a @KritixiLithos
-1 byte gracias a @FlipTack
-2 bytes gracias a @ElPedro

Jalea , 2 bytes

Æn

Pruébalo en línea!

Esto toma implícitamente la entrada z y, de acuerdo con el manual, genera la prima más cercana estrictamente mayor que z.

Oasis , 2 bytes

Corre con la -nbandera.

Código:

p

Pruébalo en línea!

Bash + coreutils, 52 bytes

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

Pruébalo en línea!

La documentación para bash y factor no especifica un valor entero máximo que puedan manejar (aunque, en la práctica, cada implementación tiene un valor entero máximo). Presumiblemente, en el GNU del futuro en sus máquinas infinitamente grandes, bash y factor tendrán enteros de tamaño ilimitado.

Máximo, 10 bytes

next_prime

Una función devuelve el primo más pequeño más grande que su argumento.

Brachylog , 2 bytes

<ṗ

Pruébalo en línea!

Explicación

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

Python con sympy, 28 bytes

import sympy
sympy.nextprime

sympy.nextprimees una función que hace lo que dice en la lata. Funciona para todas las carrozas.

repl.it

Python, 66 59 bytes

-4 bytes gracias a Lynn (uso -~)
-3 bytes gracias a FlipTack (uso andy or, permitiendo ...==1cambiar a una ...-1condición).

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

repl.it

Una función recursiva que cuenta hasta que nse encuentra un primo al probar que solo existe un número hastan-1 que lo divide (es decir, 1). Funciona para todos los enteros, genera un error para las carrozas.

Funciona en 2.7.8 y 3.5.2, no funciona en 3.3.3 (error de sintaxis debido a la falta de espacio entre ==1y 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

Sin incorporaciones, si las hay.

-30 eliminando espacios en blanco y -1 cambiando b%i==0ab%i<1

Perl 6 , 25 bytes

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

Cómo funciona

{                       }  # 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..^$_},$_^..*}

Con ineficaces pruebas de primalidad personalizadas.

Cómo funciona

La estructura externa es la misma que la anterior, pero el predicado pasado a first(para decidir si un número dado es primo), ahora es:

{               }  # 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

Pruébalo aquí!

4 bytes, sin competencia

(Intérprete actualizado desde el desafío publicado)

~p<h

Pruébalo aquí!

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

J, 4 bytes

4&p:

Simple incorporado para el próximo prime.

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

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

Pruébalo en línea!

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

Ingrese el número después de presionar Retorno (ingrese 12345 en el ejemplo a continuación, salidas 12347):

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

Cómo funciona

• Defina una cadena de 1's que tenga longitud ++$_, donde $_inicialmente es el valor de entrada
• La expresión regular verifica si la cadena de 1s es de longitud no principal (explicado aquí ).
• Si la longitud de la cadena no es primo, la verificación se vuelve a evaluar para el siguiente entero ( ++$_)
• Si la longitud de la cadena es primo, el whilebucle implícito sale e -pimprime el valor de$_
• Nota: no es necesario manejar el caso "1"de borde de longitud 1 porque nunca se usará para valores menores que 1, según la especificación.

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 gracias @Poke

Sin golf:

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);
  }
}

Pruébalo aquí.

Algunos ejemplos de entradas / salidas:

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

QBIC , 34 bytes

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

Basado en este probador de primalidad QBIC . Explicación:

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

Salida

3

MATL, 3 bytes

_Yq 

La función Yqdevuelve el próximo primo del valor absoluto de la entrada si la entrada es negativa, por lo que implícitamente tomamos la entrada, la negamos ( _) y encontramos el siguiente primo usando Yq.

Pruébalo en línea!

Haskell, 42 46 43 bytes

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

El código habitual para la fuerza bruta.

Por supuesto, esto encuentra el siguiente número primo más pequeño después den . No hay mayor prima.

Funciona para n > 0 .

editar: Asume que nes primo. Gracias al consejo de @Laikoni en los comentarios .

SimpleTemplate, 132 bytes

El algoritmo es terrible, ya que tengo que hacer mi propio código para verificar si un número es primo o no.
Resultó ser horrible, pero funciona.

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

Recibe el número como primer argumento, generando el resultado.

Sin golf:

{@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}

¿Algún consejo sobre cómo eliminar eso ú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, a diferencia de otros idiomas, tiene un tamaño entero máximo. Una vez que un número sea mayor que 2 ³² , las cosas dejan de funcionar correctamente y Lua comienza a intentar hacer estimaciones en lugar de valores exactos.

Como tal, tuve que implementar un nuevo método para almacenar números, en particular, los almacené como cadenas Base10, porque Lua no tiene un límite de tamaño en las cadenas, que no sea el tamaño de la memoria.

Siento que esta respuesta es mucho más al espíritu de la pregunta, ya que tiene que implementar enteros de precisión arbitrarios, así como una prueba principal.

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)

Aunque lo anterior usa Metatables, en lugar de solo funciones regulares como la respuesta real, que resultó más pequeña.

Rubí, 28 + 6 = 34 bytes

Usa la -rprimebandera.

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

Versión no recursiva para 31 + 6 = 37 bytes:

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

Python + primefac , 34 32 bytes

No es tan corto como usar sympy(otra respuesta ya lo usa), pero sigue siendo bastante corto y es mucho más rápido.

import primefac as p
p.nextprime

Pruébalo en línea

La entrada de 2**2000completa en un par de segundos.

Japt, 6 bytes

_j}aUÄ

Ejecútalo en línea.