Intro:

Vous avez accidentellement corrompu l'écoulement du temps avec un appareil que vous avez conçu pour le plaisir, qui s'est avéré être une machine à voyager dans le temps. En conséquence, vous avez été poussé vers un avenir lointain. Vous vous êtes rendu compte que l'informatique, la puissance de traitement et les ordinateurs en général ont évolué énormément, infiniment pour être précis . Vous vous prenez donc un ordinateur avec une mémoire et une puissance de traitement infinies. Vous ne savez pas comment il peut avoir une mémoire infinie et une puissance de traitement infinie, mais vous l'acceptez et revenez au présent.

Défi:

Vous avez entendu dire que la personne qui a découvert le plus gros prime actuellement 2^74,207,281 − 1payé 100 000 $. Vous décidez de créer un programme qui trouve le premier prime, car vous voulez récupérer l'argent que vous avez dépensé pour l'ordinateur. Vous en créez un qui prend l'entrée d'un nombre et trouve le nombre premier suivant, soit par bruteforcing, soit par toute autre méthode.

Clarifications: Vous avez une machine hypothétique avec une mémoire et une puissance de traitement infinies. Votre programme NE DOIT PAS être limité (par exemple: les int de C # peuvent stocker de -2,147,483,648à 2,147,483,647), et bien votre programme doit être capable de stocker et de fonctionner avec n'importe quel nombre de n'importe quelle taille. Vous avez des ressources infinies, donc vous ne devriez pas vous soucier de manquer de mémoire si vous le permettez.

Exemple d'E / S:
Entrée: le plus grand nombre découvert actuellement avec 22 338 618 chiffres.
Sortie: exactement le premier prime

De toute évidence, vous n'avez pas à prouver que cela fonctionne, car cela prendrait une tonne de temps à calculer dans une machine physique. Mais si vous avez déplacé votre programme vers une machine hypothétique avec une puissance de traitement / mémoire infinie, il devrait calculer instantanément.

Trouver le premier nombre premier et vérifier si un nombre est un nombre premier sont deux choses complètement différentes

Mathematica, 9 octets

NextPrime

Python 3 , 45 octets

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

Essayez-le en ligne!

Python 2, 78 77 76 74 octets

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

-1 octet grâce à @KritixiLithos
-1 octet grâce à @FlipTack
-2 octets grâce à @ElPedro

Gelée , 2 octets

Æn

Essayez-le en ligne!

Cela prend implicitement l'entrée z et, selon le manuel, génère le plus proche premier strictement supérieur à z.

Oasis , 2 octets

Courez avec le -ndrapeau.

Code:

p

Essayez-le en ligne!

Bash + coreutils, 52 octets

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

Essayez-le en ligne!

La documentation de bash et factor ne spécifie pas une valeur entière maximale qu'ils peuvent gérer (bien que, dans la pratique, chaque implémentation ait une valeur entière maximale). Vraisemblablement, dans le GNU du futur sur vos machines infiniment grandes, bash et factor auront des entiers de taille illimitée.

Maxima, 10 octets

next_prime

Une fonction renvoie le plus petit nombre premier plus grand que son argument.

Brachylog , 2 octets

<ṗ

Essayez-le en ligne!

Explication

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

Python avec sympy, 28 octets

import sympy
sympy.nextprime

sympy.nextprimeest une fonction qui fait ce qu'elle dit sur l'étain. Fonctionne pour tous les flotteurs.

repl.it

Python, 66 59 octets

-4 octets grâce à Lynn (utilisation -~)
-3 octets grâce à FlipTack (utilisation andet or, permettant ...==1de passer à une ...-1condition.)

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

repl.it

Une fonction récursive qui compte jusqu'à nce qu'un nombre premier soit trouvé en testant qu'un seul nombre existe jusqu'àn-1 celui qui le divise (c'est-à-dire 1). Fonctionne pour tous les entiers, déclenche une erreur pour les flottants.

Fonctionne sur 2.7.8 et 3.5.2, ne fonctionne pas sur 3.3.3 (erreur de syntaxe due au manque d'espace entre ==1et else)

Python, 114 83 octets

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

Sans builtins, s'il y en a.

-30 en supprimant les espaces et -1 en passant b%i==0àb%i<1

Perl 6 , 25 octets

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

Comment ça fonctionne

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

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

Avec des tests de primalité personnalisés inefficaces.

Comment ça fonctionne

La structure extérieure est la même que ci-dessus, mais le prédicat passé à first(pour décider si un nombre donné est premier) est maintenant:

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

~p#Q>)h

Essayez-le ici!

4 octets, sans concurrence

(L'interprète a été mis à jour depuis la publication du défi)

~p<h

Essayez-le ici!

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

J, 4 octets

4&p:

Simple intégré pour le prochain prime.

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

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

Essayez-le en ligne!

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 octets (29 +1 pour -p):

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

Usage

Entrez le nombre après avoir appuyé sur retour (entrez 12345 dans l'exemple ci-dessous, sortez 12347):

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

Comment ça fonctionne

• Définissez une chaîne de 1's qui a une longueur ++$_, où$_ est initialement la valeur d'entrée
• L'expression régulière vérifie si la chaîne de 1s n'est pas de longueur première (expliqué ici ).
• Si la longueur de la chaîne n'est pas première, la vérification est réévaluée pour le prochain entier (++$_ )
• Si la longueur de la chaîne est première, la whileboucle implicite se ferme et -paffiche la valeur de$_
• Remarque: il n'est pas nécessaire de gérer le cas "1"de bord de longueur 1 car il ne sera jamais utilisé pour des valeurs inférieures à 1, selon la spécification.

Java 7, 373 343 334 303 268 octets

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 octets merci @Poke

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

Essayez-le ici.

Quelques exemples d'entrées / sorties:

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

QBIC , 34 octets

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

Basé sur ce testeur de primalité QBIC . Explication:

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

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

Usage

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

Production

3

MATL, 3 octets

_Yq 

La fonction Yqrenvoie le nombre premier suivant de la valeur absolue de l'entrée si l'entrée est négative, donc nous saisissons implicitement l'entrée, la nions ( _) et trouvons le nombre premier suivant en utilisant Yq.

Essayez-le en ligne!

Haskell, 42 46 43 octets

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

le code habituel pour la force brute.

Bien sûr, cela trouve le plus petit nombre premier suivant n. Il n'y a pas de plus gros prime.

Fonctionne pour n > 0 .

modifier: Suppose nest premier. Merci aux conseils de @Laikoni dans les commentaires .

SimpleTemplate, 132 octets

L'algorithme est terrible, car je dois faire mon propre code pour vérifier si un nombre est premier ou non.
Cela s'est avéré horrible, mais ça marche.

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

Reçoit le nombre comme premier argument, produisant le résultat.

Non 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}

Des conseils sur la façon de supprimer ce dernier @if?

Lua, 876 octets

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, contrairement à certaines autres langues, a une taille entière maximale. Une fois qu'un nombre dépasse 2 ³² , les choses cessent de fonctionner correctement et Lua commence à essayer de faire des estimations au lieu de valeurs exactes.

En tant que tel, j'ai dû implémenter une nouvelle méthode de stockage des nombres, en particulier, je les ai stockés en tant que chaînes Base10, car Lua n'a pas de limite de taille sur les chaînes, autre que la taille de la mémoire.

Je pense que cette réponse est beaucoup plus à l'esprit de la question, car elle doit elle-même implémenter des entiers de précision arbitraires, ainsi qu'un premier critère.

Expliqué

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

Bien que ce qui précède utilise des métatables, au lieu de simplement des fonctions régulières comme la réponse réelle, qui a fonctionné plus petit.

Ruby, 28 + 6 = 34 octets

Utilise le -rprimedrapeau.

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

Version non récursive pour 31 + 6 = 37 octets:

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

Python + primefac , 34 32 octets

Pas tout à fait aussi court que l'utilisation sympy(une autre réponse l'utilise déjà), mais c'est toujours assez court et c'est beaucoup plus rapide.

import primefac as p
p.nextprime

Essayez-le en ligne

La saisie de se 2**2000termine en quelques secondes.

Japt, 6 octets

_j}aUÄ

Exécutez-le en ligne.