Вступление:

Вы случайно испортили поток времени с помощью устройства, созданного вами для удовольствия, которое оказалось машиной времени. В результате вы оказались в далеком будущем. Вы поняли, что вычислительная мощность, вычислительная мощность и компьютеры в целом эволюционировали в огромном количестве, а точнее , в бесконечном количестве . Таким образом, вы получаете компьютер с бесконечной памятью и вычислительной мощностью. Вы не представляете, как оно может обладать бесконечной памятью и бесконечной вычислительной мощностью, но вы просто принимаете это и возвращаетесь в настоящее.

Вызов:

Вы слышали, что человек, который обнаружил самый большой в настоящее время премьер, 2^74,207,281 − 1получил 100 000 долларов. Вы решаете создать программу, которая найдет следующее простое число, поскольку вы хотите вернуть деньги, потраченные на компьютер. Вы создаете тот, который принимает ввод числа и находит следующее простое число, используя брутфорс или любой другой метод.

Пояснения: у вас есть гипотетическая машина с бесконечной памятью и вычислительной мощностью. Ваша программа НЕ ДОЛЖНА быть ограничена (например, C # могут хранить от int -2,147,483,648до 2,147,483,647), так что ваша программа должна быть в состоянии хранить и работать с любым числом любого размера. У вас есть бесконечные ресурсы, поэтому вам не нужно беспокоиться, не хватит ли вам памяти, если вы позволите это.

Пример ввода / вывода:
Ввод: наибольшее обнаруженное простое число с 22 338 618 цифрами.
Вывод: точно следующий штрих

Очевидно, вам не нужно доказывать, что это работает, так как для вычислений на физической машине потребуется куча времени. Но если вы переместили вашу программу на гипотетический компьютер с бесконечной вычислительной мощностью / памятью, она должна вычисляться мгновенно.

Поиск следующего простого числа и проверка, является ли число простым числом, это две совершенно разные вещи.

Mathematica, 9 байт

NextPrime

Python 3 , 45 байт

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

Попробуйте онлайн!

Python 2, 78 77 76 74 байта

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

-1 байт благодаря @KritixiLithos
-1 байт благодаря @FlipTack
-2 байт благодаря @ElPedro

Желе , 2 байта

Æn

Попробуйте онлайн!

Это неявно принимает входные данные z и, согласно руководству, генерирует ближайший простое число, строго большее, чем z.

Оазис , 2 байта

Беги с -nфлагом.

Код:

p

Попробуйте онлайн!

Bash + coreutils, 52 байта

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

Попробуйте онлайн!

В документации по bash и factor не указывается максимальное целочисленное значение, которое они могут обработать (хотя на практике каждая реализация имеет максимальное целочисленное значение). Предположительно, в GNU будущего на ваших бесконечно больших машинах bash и factor будут иметь целые числа неограниченного размера.

Максима, 10 байт

next_prime

Функция возвращает наименьшее простое число, большее, чем ее аргумент.

Брахилог , 2 байта

<ṗ

Попробуйте онлайн!

объяснение

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

Python с симпой, 28 байт

import sympy
sympy.nextprime

sympy.nextprimeэто функция, которая делает то, что говорит на банке. Работает на все поплавки.

repl.it

Python, 66 59 байт

-4 байта благодаря Lynn (используйте -~)
-3 байта благодаря FlipTack (используйте andи or, позволяя ...==1переключиться на ...-1состояние.)

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

repl.it

Рекурсивная функция, которая считает от n простого числа тех пор, пока не будет найдено простое число, проверяя, что существует только одно число n-1, делающее его (т.е. 1). Работает для всех целых чисел, вызывает ошибку для чисел с плавающей запятой.

Работает на 2.7.8 и 3.5.2, не работает на 3.3.3 (синтаксическая ошибка из-за недостатка места между ==1и else)

Python, 114 83 байта

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

Без встроенных, если они есть.

-30 путем удаления пробелов и -1 путем изменения b%i==0наb%i<1

Perl 6 , 25 байт

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

Как это устроено

{                       }  # 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 байта

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

С неэффективным пользовательским тестированием первичности.

Как это устроено

Внешняя структура такая же, как и выше, но предикат, переданный first(чтобы определить, является ли данное число простым), теперь:

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

Пайк, 8 7 байт

~p#Q>)h

Попробуй это здесь!

4 байта, неконкурентные

(Интерпретатор обновлен с момента публикации запроса)

~p<h

Попробуй это здесь!

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

J, 4 байта

4&p:

Простой встроенный для следующего премьер.

05AB1E , 16 13 байтов (Emigna @ -3 байта)

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

Попробуйте онлайн!

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 байт (29 +1 для -p ):

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

использование

Введите число после нажатия возврата (введите 12345 в примере ниже, выводит 12347):

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

Как это устроено

• Определите строку 1's, которая имеет длину++$_ , где $_изначально находится входное значение
• Регулярное выражение проверяет, является ли строка 1s не простой длины (объяснено здесь ).
• Если длина строки не проста, проверка переоценивается для следующего целого числа (++$_ )
• Если длина строки проста, неявный whileцикл завершается и -pпечатает значение$_
• Примечание: нет необходимости обрабатывать крайний край "1"длины 1, потому что он никогда не будет использоваться для значений, меньших, чем 1в спецификации.

Java 7, 373 343 334 303 268 байт

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 байт спасибо @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);
  }
}

Попробуй это здесь.

Некоторые примеры ввода / вывода:

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

QBIC , 34 байта

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

Основанный на этом тестере первичности QBIC . Объяснение:

:{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 байт

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

использование

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

Выход

3

MATL, 3 байта

_Yq 

Функция Yqвозвращает следующее простое число абсолютного значения входного значения, если входное значение является отрицательным, поэтому мы неявно захватываем входное значение, отменяем его ( _) и находим следующее простое число, используя Yq.

Попробуйте онлайн!

Хаскелл, 42 46 43 байта

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

обычный код для грубой силы.

Конечно, это находит следующее наименьшее простое число послеn . Там не самый большой премьер.

Работает при n > 0 .

Редактировать: Предполагается n, прост. Благодаря совету @Laikoni в комментариях .

SimpleTemplate, 132 байта

Алгоритм ужасен, так как я должен сделать свой собственный код, чтобы проверить, является ли число простым или нет.
Это оказалось ужасно, но работает.

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

Получает число в качестве первого аргумента, выводя результат.

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}

Любые советы о том, как удалить этот последний @if?

Луа, 876 байт

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, в отличие от некоторых других языков, имеет максимальный целочисленный размер. Как только число становится больше 2 ³² , все перестает работать правильно, и Lua начинает пытаться делать оценки вместо точных значений.

Таким образом, мне пришлось реализовать новый метод хранения чисел, в частности, я сохранил их как строки Base10, потому что у Lua нет ограничения по размеру для строк, кроме размера памяти.

Я чувствую, что этот ответ гораздо больше относится к духу вопроса, поскольку он сам должен реализовывать произвольные целые числа точности, а также простой тест.

Разъяснения

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

Хотя в приведенном выше примере используются метатаблицы, а не просто обычные функции, такие как фактический ответ, который получился меньше.

Рубин, 28 + 6 = 34 байта

Использует -rprimeфлаг.

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

Нерекурсивная версия для 31 + 6 = 37 байт:

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

Python + primefac , 34 32 байта

Не такой короткий, как использование sympy(другой ответ уже использует это), но он все еще довольно короткий и намного быстрее.

import primefac as p
p.nextprime

Попробуйте онлайн

Ввод 2**2000завершается за пару секунд.

Japt, 6 байт

_j}aUÄ

Запустите его онлайн.