Pengantar:

Anda secara tidak sengaja merusak aliran waktu dengan perangkat yang Anda buat untuk kesenangan, yang ternyata adalah mesin waktu. Akibatnya, Anda terdorong ke masa depan yang jauh. Anda menyadari bahwa komputasi, kekuatan pemrosesan, dan komputer pada umumnya telah berkembang dengan jumlah yang sangat besar, jumlah yang tidak terbatas tepatnya . Jadi, Anda mengambil sendiri komputer dengan memori tak terbatas dan kekuatan pemrosesan. Anda tidak tahu bagaimana itu dapat memiliki memori tak terbatas dan kekuatan pemrosesan tak terbatas, tetapi Anda hanya menerimanya dan kembali ke masa sekarang.

Tantangan:

Anda mendengar bahwa orang yang menemukan prime terbesar saat ini 2^74,207,281 − 1dibayar $ 100.000. Anda memutuskan untuk membuat program yang menemukan prime berikutnya, karena Anda ingin mendapatkan kembali uang yang Anda habiskan untuk komputer. Anda membuat satu yang mengambil input dari suatu angka, dan menemukan bilangan prima berikutnya, baik dengan memaksa atau metode lain.

Klarifikasi: Anda memiliki mesin hipotetis dengan memori tak terbatas dan kekuatan pemrosesan. Program Anda TIDAK HARUS dibatasi (misalnya: int C # dapat menyimpan dari -2,147,483,648hingga 2,147,483,647), baik program Anda harus dapat menyimpan, dan bekerja dengan jumlah berapapun berapapun. Anda memiliki sumber daya tanpa batas, jadi Anda tidak perlu peduli apakah Anda kehabisan memori jika Anda mengizinkannya.

Contoh I / O:
Input: Prime yang ditemukan terbesar saat ini dengan 22.338.618 digit.
Output: Tepatnya prime berikutnya

Jelas, Anda tidak perlu membuktikan bahwa itu bekerja, karena akan membutuhkan waktu satu ton untuk menghitung dalam mesin fisik. Tetapi jika Anda memindahkan program Anda ke mesin hipotetis dengan daya pemrosesan / memori yang tak terbatas, itu harus menghitung langsung.

Menemukan perdana berikutnya dan memeriksa apakah suatu bilangan prima, adalah dua hal yang sama sekali berbeda

Mathematica, 9 byte

NextPrime

Python 3 , 45 byte

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

Cobalah online!

Python 2, 78 77 76 74 byte

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

-1 byte terima kasih kepada @KritixiLithos
-1 byte terima kasih kepada @FlipTack
-2 byte terima kasih kepada @ElPedro

Jelly , 2 byte

Æn

Cobalah online!

Ini secara implisit mengambil input z dan, menurut manual, menghasilkan bilangan prima terdekat yang benar-benar lebih besar dari z.

Oasis , 2 byte

Jalankan dengan -nbendera.

Kode:

p

Cobalah online!

Bash + coreutils, 52 byte

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

Cobalah online!

Dokumentasi untuk bash dan faktor tidak menentukan nilai integer maksimum yang dapat mereka tangani (walaupun, dalam praktiknya, setiap implementasi memang memiliki nilai integer maksimum). Agaknya, di GNU masa depan pada mesin Anda yang tak terhingga besar, bash dan faktor akan memiliki bilangan bulat ukuran tak terbatas.

Maksima, 10 byte

next_prime

Suatu fungsi mengembalikan bilangan prima terkecil lebih besar dari argumennya.

Brachylog , 2 byte

<ṗ

Cobalah online!

Penjelasan

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

Python dengan sympy, 28 byte

import sympy
sympy.nextprime

sympy.nextprimeadalah fungsi yang melakukan apa yang tertulis di kaleng. Bekerja untuk semua pelampung.

repl.it

Python, 66 59 byte

-4 byte terima kasih kepada Lynn (gunakan -~)
-3 byte terima kasih kepada FlipTack (gunakan anddan or, yang memungkinkan ...==1untuk dialihkan ke suatu ...-1kondisi.)

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

repl.it

Fungsi rekursif yang dihitung dari nsampai prima ditemukan dengan menguji bahwa hanya ada satu angka n-1yang membaginya (yaitu 1). Berfungsi untuk semua bilangan bulat, menimbulkan kesalahan untuk float.

Bekerja pada 2.7.8 dan 3.5.2, tidak berfungsi pada 3.3.3 (kesalahan sintaksis karena kurangnya ruang antara ==1dan else)

Python, 114 83 byte

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

Tanpa builtin, jika ada.

-30 dengan menghapus spasi dan -1 dengan mengubah b%i==0keb%i<1

Perl 6 , 25 byte

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

Bagaimana itu bekerja

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

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

Dengan pengujian kebiasaan primitif yang tidak efisien.

Bagaimana itu bekerja

Struktur luar sama dengan di atas, tetapi predikat yang diteruskan ke first(untuk memutuskan apakah angka yang diberikan adalah prima), sekarang:

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

~p#Q>)h

Coba di sini!

4 byte, tidak bersaing

(Penerjemah diperbarui sejak tantangan diposting)

~p<h

Coba di sini!

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

J, 4 byte

4&p:

Sederhana dibangun untuk perdana berikutnya.

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

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

Cobalah 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 byte (29 +1 untuk -p):

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

Pemakaian

Masukkan nomor setelah menekan kembali (input 12345 pada contoh di bawah, output 12347):

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

Bagaimana itu bekerja

• Tentukan string 1yang memiliki panjang ++$_, di mana $_awalnya nilai input
• Regex memeriksa untuk melihat apakah string 1s adalah panjang non-prima (dijelaskan di sini ).
• Jika panjang string non-prima, centang dievaluasi ulang untuk bilangan bulat berikutnya ( ++$_)
• Jika panjang string prima, whileloop implisit keluar dan -pmencetak nilai$_
• Catatan: tidak perlu menangani kasing sisi "1"panjang 1 karena tidak akan pernah digunakan untuk nilai kurang dari 1, sesuai spesifikasi.

Java 7, 373 343 334 303 268 byte

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 byte terima kasih @Poke

Tidak Disatukan:

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

Coba di sini.

Beberapa contoh input / output:

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

QBIC , 34 byte

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

Didasarkan pada penguji primitif QBIC ini . Penjelasan:

:{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;}}

Pemakaian

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

Keluaran

3

MATL, 3 byte

_Yq 

Fungsi Yqmengembalikan prime berikutnya dari nilai absolut input jika input negatif sehingga kami secara implisit mengambil input, meniadakannya ( _) dan menemukan prime berikutnya menggunakan Yq.

Cobalah secara Online!

Haskell, 42 46 43 byte

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

kode biasa untuk brute force.

Tentu saja ini menemukan bilangan prima terkecil berikutnya setelahnya n. Tidak ada prime terbesar.

Bekerja untuk n > 0 .

sunting: Asumsinya nprima. Terima kasih atas saran @Laikoni di komentar .

SimpleTemplate, 132 byte

Algoritma itu mengerikan, karena saya harus melakukan kode saya sendiri untuk memeriksa apakah suatu bilangan prima atau tidak.
Itu terbukti mengerikan, tetapi berhasil.

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

Menerima nomor sebagai argumen pertama, mengeluarkan hasilnya.

Tidak Disatukan:

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

Adakah tips tentang cara menghapus yang terakhir @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, tidak seperti beberapa bahasa lain, memang memiliki Ukuran Integer Maksimal. Setelah angka menjadi lebih besar dari 2 ³² , hal-hal berhenti berfungsi dengan benar, dan Lua mulai mencoba membuat estimasi, bukan nilai yang tepat.

Karena itu, saya harus menerapkan metode baru untuk menyimpan angka, khususnya, saya telah menyimpannya sebagai string Base10, karena Lua tidak memiliki batas ukuran pada String, selain dari ukuran memori.

Saya merasa jawaban ini lebih ke Roh pertanyaan, karena harus menerapkan bilangan bulat presisi sewenang-wenang, serta ujian utama.

Dijelaskan

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

Meskipun di atas menggunakan Metatables, bukan hanya fungsi biasa seperti jawaban yang sebenarnya, yang bekerja lebih kecil.

Ruby, 28 + 6 = 34 byte

Menggunakan -rprimebendera.

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

Versi non-rekursif untuk 31 + 6 = 37 byte:

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

Python + primefac , 34 32 byte

Tidak sesingkat menggunakan sympy(jawaban lain sudah menggunakan itu), tetapi masih cukup pendek, dan itu jauh lebih cepat.

import primefac as p
p.nextprime

Cobalah online

Input 2**2000selesai dalam beberapa detik.

Japt, 6 byte

_j}aUÄ

Jalankan secara online.