Intro:

Sie haben versehentlich den Zeitfluss mit einem Gerät verfälscht, das Sie zum Spaß gemacht haben und das sich als Zeitmaschine herausstellte. Infolgedessen wurdest du in die ferne Zukunft gedrängt. Sie haben festgestellt, dass sich Computer, Rechenleistung und Computer im Allgemeinen enorm weiterentwickelt haben, um genau zu sein , unendlich viel . So schnappen Sie sich einen Computer mit unendlich viel Speicher und Rechenleistung. Sie haben keine Ahnung, wie es unendlichen Speicher und unendliche Rechenleistung haben kann, aber Sie akzeptieren es einfach und kehren in die Gegenwart zurück.

Herausforderung:

Sie haben gehört, dass die Person, die den derzeit größten Prime entdeckt 2^74,207,281 − 1hat, 100.000 US-Dollar erhalten hat. Sie beschließen, ein Programm zu erstellen, das die nächste Primzahl findet, da Sie das Geld zurückerhalten möchten, das Sie für den Computer ausgegeben haben. Sie erstellen eine, die eine Zahl eingibt und die nächste Primzahl entweder durch Bruteforcing oder eine andere Methode findet.

Erläuterungen: Sie haben eine hypothetische Maschine mit unbegrenztem Speicher und Rechenleistung. Ihr Programm darf NICHT eingeschränkt sein (zB: C # 's Int's können von -2,147,483,648bis speichern 2,147,483,647), und Ihr Programm muss in der Lage sein, eine beliebige Anzahl beliebiger Größen zu speichern und damit zu arbeiten. Sie haben unendlich viele Ressourcen, daher sollte es Sie nicht interessieren, ob Ihnen der Speicher ausgeht, wenn Sie dies zulassen.

Beispiel I / O:
Eingabe: Die aktuell größte entdeckte Primzahl mit 22.338.618 Stellen.
Ausgabe: Genau die nächste Primzahl

Offensichtlich müssen Sie nicht beweisen, dass es funktioniert, da es eine Menge Zeit in Anspruch nehmen würde, um in einer physischen Maschine zu rechnen. Wenn Sie Ihr Programm jedoch auf eine hypothetische Maschine mit unendlicher Rechenleistung / unbegrenztem Arbeitsspeicher verschoben haben, sollte es sofort berechnet werden.

Das Finden der nächsten Primzahl und das Überprüfen, ob eine Zahl eine Primzahl ist, sind zwei völlig verschiedene Dinge

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)

Probieren Sie es 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 dank @KritixiLithos
-1 Byte dank @FlipTack
-2 Byte dank @ElPedro

Gelee , 2 Bytes

Æn

Probieren Sie es online!

Dies erfordert implizit die Eingabe von z und generiert laut Handbuch die nächstliegende Primzahl, die strikt größer als z ist.

Oase , 2 Bytes

Laufen Sie mit der -nFlagge.

Code:

p

Probieren Sie es online!

Bash + Coreutils, 52 Bytes

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

Probieren Sie es online!

In der Dokumentation für bash und factor wird kein maximaler ganzzahliger Wert angegeben, der verarbeitet werden kann (obwohl in der Praxis jede Implementierung einen maximalen ganzzahligen Wert hat). Vermutlich werden in der GNU der Zukunft auf Ihren unendlich großen Maschinen Bash und Factor Ganzzahlen mit unbegrenzter Größe haben.

Maxima, 10 Bytes

next_prime

Eine Funktion gibt die kleinste Primzahl zurück, die größer als ihr Argument ist.

Brachylog , 2 Bytes

<ṗ

Probieren Sie es online!

Erläuterung

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

Python mit Sympy, 28 Bytes

import sympy
sympy.nextprime

sympy.nextprimeist eine Funktion, die das tut, was sie verspricht. Funktioniert für alle Schwimmer.

repl.it

Python, 66 59 Bytes

-4 Bytes dank Lynn (benutze -~)
-3 Bytes dank FlipTack (benutze andund or, ...==1um in einen ...-1Zustand versetzt zu werden.)

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

repl.it

Eine rekursive Funktion, die nbis zum Auffinden einer Primzahl zählt, indem geprüft wird, ob nur eine Zahl existiert, bis n-1diese geteilt wird (dh 1). Funktioniert für alle ganzen Zahlen, löst einen Fehler für Floats aus.

Funktioniert mit 2.7.8 und 3.5.2, funktioniert nicht mit 3.3.3 (Syntaxfehler aufgrund fehlenden Abstands zwischen ==1und 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

Ohne Builtins, wenn es welche gibt.

-30 durch Entfernen von Leerzeichen und -1 durch Ändern b%i==0aufb%i<1

Perl 6 , 25 Bytes

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

Wie es funktioniert

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

Mit ineffizienten benutzerdefinierten Primalitätstests.

Wie es funktioniert

Die äußere Struktur ist dieselbe wie oben, aber das Prädikat, an das übergeben wird first(um zu entscheiden, ob eine bestimmte Zahl eine Primzahl ist), lautet jetzt:

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

Probieren Sie es hier aus!

4 Bytes, nicht konkurrierend

(Dolmetscher aktualisiert seit dem Absenden der Challenge)

~p<h

Probieren Sie es hier aus!

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

J, 4 Bytes

4&p:

Einfach für den nächsten Prime eingebaut.

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

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

Probieren Sie es 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 für -p):

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

Verwendung

Geben Sie die Nummer ein, nachdem Sie die Eingabetaste gedrückt haben (Eingabe 12345 im folgenden Beispiel, Ausgabe 12347):

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

Wie es funktioniert

• Definieren Sie eine Zeichenfolge mit der 1Länge ++$_, wobei $_anfangs der Eingabewert ist
• Der Regex prüft, ob die Zeichenfolge von 1s keine Primzahllänge hat ( hier erklärt ).
• Wenn die Zeichenfolgenlänge keine Primzahl ist, wird die Prüfung für die nächste Ganzzahl ( ++$_) erneut ausgewertet.
• Wenn die Zeichenfolgenlänge eine Primzahl ist, wird die implizite whileSchleife beendet und -pder Wert von ausgegeben$_
• Hinweis: Es ist nicht erforderlich, den Kantenfall "1"der Länge 1 zu behandeln, da er niemals für Werte verwendet wird, die niedriger sind als 1gemäß der Spezifikation.

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

Probieren Sie es hier aus.

Einige Beispiele für Ein- / Ausgänge:

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

QBIC , 34 Bytes

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

Basierend auf diesem QBIC-Primalitätstester . Erläuterung:

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

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

Verwendung

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

Ausgabe

3

MATL, 3 Bytes

_Yq 

Die Funktion Yqgibt die nächste Primzahl des Absolutwerts der Eingabe zurück, wenn die Eingabe negativ ist. Daher greifen wir implizit auf die Eingabe, negieren sie ( _) und suchen die nächste Primzahl mit Yq.

Probieren Sie es online!

Haskell, 42 46 43 Bytes

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

der übliche Code für Brute Force.

Natürlich findet diese die nächste kleinste Primzahl nach n. Es gibt keine größte Primzahl.

Funktioniert für n > 0 .

edit: Angenommen, nist prime. Danke an @Laikoni 's Rat in den Kommentaren .

SimpleTemplate, 132 Bytes

Der Algorithmus ist schrecklich, da ich meinen eigenen Code machen muss, um zu prüfen, ob eine Zahl eine Primzahl ist oder nicht.
Es hat sich als schrecklich erwiesen, funktioniert aber.

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

Erhält die Zahl als erstes Argument und gibt das Ergebnis aus.

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}

Irgendwelche Tipps, wie man das zuletzt entfernt @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 hat im Gegensatz zu einigen anderen Sprachen eine maximale Ganzzahlgröße. Sobald eine Zahl größer als 2 ^{32 wird} , funktionieren die Dinge nicht mehr richtig, und Lua versucht, Schätzungen anstelle genauer Werte vorzunehmen.

Als solches musste ich eine neue Methode zum Speichern von Zahlen implementieren, insbesondere habe ich sie als Base10-Zeichenfolgen gespeichert, da Lua keine Größenbeschränkung für Zeichenfolgen außer der Größe des Speichers hat.

Ich bin der Meinung, dass diese Antwort viel mehr dem Geist der Frage entspricht, da sie selbst willkürliche Ganzzahlen sowie einen Primärtest implementieren muss.

Erklärt

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

Obwohl die oben genannten Metatables verwendet, statt nur reguläre Funktionen wie die eigentliche Antwort, die kleiner ausgearbeitet hat.

Ruby, 28 + 6 = 34 Bytes

Verwendet die -rprimeFlagge.

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

Nichtrekursive Version für 31 + 6 = 37 Bytes:

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

Python + Primefac , 34 32 Bytes

Nicht ganz so kurz wie using sympy(eine andere Antwort verwendet das bereits), aber es ist immer noch ziemlich kurz und viel schneller.

import primefac as p
p.nextprime

Probieren Sie es online aus

Die Eingabe von wird 2**2000in wenigen Sekunden abgeschlossen.

Japt, 6 Bytes

_j}aUÄ

Führen Sie es online aus.