Eine Primzahllücke ist der Unterschied zwischen zwei aufeinanderfolgenden Primzahlen. Genauer gesagt, wenn p und q Primzahlen mit p < q sind und p + 1, p + 2, ..., q - 1 keine Primzahlen sind, definieren die Primzahlen p und q eine Lücke von n = q - p . Der Spalt wird gesagt werden gestartet durch p und hat Länge n .

Es ist bekannt, dass beliebig große Primlücken bestehen. Das heißt, wenn n gegeben ist, existiert eine Primzahllücke der Länge n oder größer. Es kann jedoch sein, dass eine Primlücke der Länge n nicht existiert (eine größere Lücke jedoch).

Die Herausforderung

Bei einer positiven Ganzzahl nwird die erste Primzahl ausgegeben, die eine Lücke von mindestens Länge beginnt n.

Als Beispiel für die Eingabe sollte 4die Ausgabe sein 7, da 7 und 11 die ersten aufeinanderfolgenden Primzahlen sind, die sich um mindestens 4 unterscheiden (die vorherigen Lücken sind 1, 2 bis 3; 2, 3 bis 5; und 2, 5) bis 7). Für die Eingabe sollte 3die Antwort auch lauten 7(es gibt keine Lücken der Länge 3).

Zusätzliche Regeln

• Der Algorithmus sollte theoretisch für beliebig hohe Werte arbeiten n. In der Praxis ist es akzeptabel, wenn das Programm durch Zeit, Speicher oder Datentypgröße begrenzt ist.

• Eingabe und Ausgabe können mit allen angemessenen Mitteln erfolgen .

• Programme oder Funktionen sind in jeder Programmiersprache zulässig . Standardlücken sind verboten.

• Kürzester Code in Bytes gewinnt.

Testfälle

Input -> Output

1        2
2        3
3        7
4        7
6        23
10       113
16       523
17       523
18       523
30       1327
50       19609
100      370261
200      20831323

Gaia , 6 Bytes

zṅọ⊃∆ṇ

Dies ist äußerst ineffizient (die 16Berechnung des Testfalls auf meinem Computer dauerte über eine Stunde).

Probieren Sie es online!

Erläuterung

Die Sequenz scheint die Eigenschaft zu haben, dass a (n) <= 2 ^ n ist .

z       Push 2^input.
 ṅ      Get the first 2^input prime numbers.
  ọ     Get the deltas of the list.
   ⊃∆   Find the index of the first that is greater than or equal to the input.
     ṇ  Push the index-th prime number.

Jelly , 10, 9, 8, 10 Bytes

Æn_$:ð1#»2

Probieren Sie es online!

Zwei Bytes gespart dank @Dennis! (und dann wegen Edge-Cases wieder hinzugefügt)

Erläuterung:

Æn          #   The next prime after 'P'
  _$        #   Minus 'P'
    :       #   Divided by 'N'
            #
            # This will give a falsy value unless the distance to the next prime is >= N
            #
     ð      # Treat all of that as a single dyad (fucntion with two arguments). 
            # We'll call it D(P, N)
            #
      1#    # Find the first 'P' where D(P, input()) is truthy
        »2  # Return the maximum of that result and 2

Mathematica, 30 Bytes

2//.x_ /;NextPrime@x-x<#:>x+1&

Probieren Sie es online!

Mathematica, 35 Bytes

(t=2;While[NextPrime@t-t<#,t++];t)&

Probieren Sie es online!

Mathematica, 77 Bytes

Prime@Min@Position[s=Differences@Prime@Range[(r=#)^3+1],#&@@Select[s,#>=r&]]&

Haskell , 106 102 93 77 73 72 Bytes

Dies erzeugt zuerst eine unendliche Liste von Primzahlen und sucht dann nach den Lücken der Primzahlen. Die Hauptliste wurde von hier genommen . Es kann wahrscheinlich gekürzt werden, aber ich habe noch nicht herausgefunden, wie :)

Danke an @BruceForte für -4 Bytes und @Zgrab für -1 Bytes!

f n=[x|(y,x)<-zip=<<tail$[n|n<-[2..],all((>0).rem n)[2..n-1]],y-x>=n]!!0

Probieren Sie es online!

Pyth - 14 Bytes

Es filtert von [1, inf), filtert nach Primalität ( P_) und dass die nächste Primzahl, die von (n, inf) gefiltert wird, ein anderes> = als die Eingabe hat.

f&P_T<tQ-fP_Yh

Test Suite .

PowerShell , 97 96 91 Byte

param($n)for($a=$b=2){for(;'1'*++$b-match'^(?!(..+)\1+$)..'){if($b-$a-ge$n){$a;exit}$a=$b}}

Probieren Sie es online!

Übernimmt die Eingabe $n, setzt $aund $bgleich und 2tritt dann in eine forEndlosschleife ein. Drinnen machen wir eine Schleife, $bbis wir zur nächsten Primzahl kommen . Dann überprüfen wir , ob $b-$a(dh die Lücke) ist -greaterthanor equal zu $n. Wenn ja, geben wir $aund aus exit. Ansonsten setzen wir $asein $bund Erhöhung $bunserer nächsten Suche und starten.

Warnung: Dies ist bei großen Eingaben langsam . Tatsächlich kann es die 50oder höhere Tests nicht innerhalb des 60er-Zeitlimits für TIO abschließen . Naja.

Schale , 13 11 10 Bytes

´ȯ!V≥⁰Ẋ-İp

Probieren Sie es online!

´       İp  -- with the primes
 ȯ!         -- get the value at position
      Ẋ-    -- where the difference of the current and next prime
   V≥⁰      -- is greater or equal than the input N

Mathematica, 39 Bytes

(For[i=2;p=NextPrime,i+#>p@i,i=p@i];i)&
(* or *)
(For[i=1;p=Prime,p@i+++#>p@i,];p[i-1])&

33-Byte-Version (nicht gültig, da nur bis zur 65535. Primzahl)

p=NextPrime;2//.i_/;p@i-i<#:>p@i&

Python 2 , 96 88 Bytes

- 8 Bytes Danke an @Maltysen

n,p,r=input(),3,[2]
while p-r[-1]<n:r+=[p]*all(p%i for i in range(2,p));p+=1
print r[-1]

Probieren Sie es online!

Perl 6 , 63 Bytes

->\d{(grep &is-prime,^∞).rotor(2=>-1).first({-d>=[-] $_})[0]}

Probieren Sie es online!

Mathematica, 37 Bytes

gNestWhile[p=NextPrime,2,p@#-#<g&]

Functionmit erstem argument g. Beginnend mit 2, wendet die Funktion p=NextPrimeso lange wiederholt an, wie sich p@#-#<g&ergibt True(die Lücke zwischen der aktuellen Primzahl und der nächsten Primzahl ist geringer als g).

R + gmp, 55 Bytes

Verwendet die nextprime-Funktion aus der gmp-Bibliothek

s=2;n=scan();while((x=gmp::nextprime(s))-s<n)s=x;cat(s)

Ruby , 61 Bytes

->g{*r,f=2,3;f+=1while r.find{|n|f%n<1}||r<<f&&g>f-z=r[-2];z}

Probieren Sie es online!

C = 141 109 Bytes; C ++, D = 141 Bytes; C #, Java = 143 Bytes

WARNUNG : NIEDRIGER LEISTUNGSALGORITHMUS

Dieser Code konnte die Hauptlücke nicht g(200)innerhalb von 10 Minuten berechnen . Für g(100), es dauerte 10 Sekunden (C ++ Version)

C ++ und D Version:

int p(int d){for(int i=2;i<=d/2;++i){if(!(d%i))return 0;}return 1;}int g(int d){int f=2,n=3;while(n-f<d){f=n;do{++n;}while(!p(n));}return f;}

C # und Java Version:

int p(int d){for(int i=2;i<=d/2;++i){if(d%i==0)return 0;}return 1;}int g(int d){int f=2,n=3;while(n-f<d){f=n;do{++n;}while(p(n)==0);}return f;}

C-Version, -32 Bytes dank ceilingcat:

i;p(d){for(i=2;d/2/i;)if(!(d%i++))return 0;return 1;}f;n;g(d){for(f=2,n=3;n-f<d;)for(f=n;!p(++n););return f;}

Unterschiede zwischen der C # / Java- und der C / C ++ / D-Version: !p(n)<==>p(n)==0

D, 127 125 122 Bytes

WARNUNG: NIEDRIGER LEISTUNGSALGORITHMUS !!

T p(T)(T d){T r;for(T i=2;i<=d/2;)r=d%i++<1||r;return r;}T g(T)(T d){T f=2,n=3;while(n-f<d){f=n;while(p(++n)){}}return f;}

Probieren Sie es online!

Wie?

HatsuPointerKun nochmal, aber ich mache die D-spezifische Zauberei.

• Das Vorlagensystem kann auf Typen schließen T p(T)(T d)und ist kürzer als C ++
• r=d%i++<1||r, D-spezifische Spielereien, funktionieren möglicherweise in C / C ++, aber ich weiß es nicht.
• p(++n)Wie oben, nicht sicher, ob es in C / C ++ funktioniert
• while(p(++n)){}Hier sieht man, warum D schlecht im Golfen ist, man kann es nicht ;als leere Aussage verwenden.

Perl 6 , 41 37 Bytes

{+(1...(^$_+*)>>.is-prime eqv!<<^$_)}

Probieren Sie es online!

Erläuterung

{                                   }  # Block taking n as $_
   1...   # Sequence 1,2,... until
       (^$_+*)  # Range [i,i+n)
              >>.is-prime  # is-prime for each
                          eqv!<<^$_  # Equals (True,False,False,False,...)?
 +(                                )  # Length of sequence

QBIC , 28 Bytes

{~µs||~s-r>=:|_Xr\r=s]]s=s+1

Erläuterung

{         DO
~µs||     IF s is prime THEN (note, s starts as 3)
~s-r>=:   IF the gap between s (current prime) and r (prev prime) is big enough
|_Xr      THEN QUIT, printing prev prime r
\r=s      ELSE (gap too small, but s is prime), set r to prime s
]]        END IF x2, leaving us in the WHILE
s=s+1     increment s, retest for primality ...

05AB1E , 9 Bytes

∞<ØD¥I@Ïн

Probieren Sie es online aus oder überprüfen Sie alle Testfälle . (Test Suite enthält nicht die letzten beiden Testfälle, da TIO für diese eine Zeitüberschreitung aufweist.)

Da die andere Frage als Betrug geschlossen ist , veröffentliche ich meine Antwort auch hier.

Erläuterung:

∞           # Get an infinite list in the range [1, ...]
 <          # Decrease it by one to make it in the range [0, ...]
  Ø         # Get for each the (0-indexed) n'th prime: [2,3,5,7,11,...]
   D        # Duplicate this list of primes
    ¥       # Get all deltas (difference between each pair): [1,2,2,4,2,...]
     I@     # Check for each if they are larger than or equal to the input
            #  i.e. 4 → [0,0,0,1,0,1,0,1,1,0,...]
       Ï    # Only keep the truthy values of the prime-list
            #  → [23,31,47,53,61,...]
        н   # And keep only the first item (which is output implicitly)
            #  → 23

Java 8, 99 92 Bytes

n->{int a=2,b=3,f,k;for(;b-a<n;)for(f=0,a=b;f<2;)for(f=++b,k=2;k<f;)f=f%k++<1?0:f;return a;}

Probieren Sie es online aus. (Größter Testfall ist ausgeschlossen, da bei TIO eine Zeitüberschreitung auftritt.)

Erläuterung:

n->{               // Method with integer as both parameter and return-type
  int a=2,b=3,     //  Prime-pair `a,b`, starting at 2,3
      f,           //  Prime-checker flag `f`, starting uninitialized
      k;           //  Temp integer, starting uninitialized
  for(;b-a         //  Loop as long as the difference between the current pair of primes
          <n;)     //  is smaller than the input
    for(f=0,       //   (Re)set the prime-checker flag to 0
        a=b;       //   Replace `a` with `b`, since we're about to search for the next prime-pair
        f<2;)      //   Inner loop as long as the prime-checker flag is still 0 (or 1)
                   //   (which means the new `b` is not a prime)
      for(f=++b,   //    Increase `b` by 1 first, and set this value to the prime-checker flag
          k=2;     //    Set `k` to 2
          k<f;)    //    Inner loop as long as `k` is still smaller than the prime-checker flag
        f=         //     Change the prime-checker flag to:
          f%k++<1? //      If the prime-checker flag is divisible by `k`
           0       //       Set the prime-checker flag to 0
          :        //      Else:
           f;      //       Leave it unchanged
                   //    (If any integer `k` in the range [2, `b`) can evenly divide `b`,
                   //     the prime-checker flag becomes 0 and the loop stops)
  return a;}       //  And finally after all the nested loops, return `a` as result

Ordentlich , 33 Bytes

{x:({v:⊟v<=-x}↦primes+2)@0@0}

Probieren Sie es online!

Oder 28 Zeichen / 34 Byte: {x:({v:⊟v≤-x}↦primes+2)@0@0}

Ich erkläre dies mit einem äquivalenten ASCII-Äquivalent:

{x:({v:(-)over v<=-x}from primes+2)@0@0}
{x:                                    }    lambda w/ parameter `x`
                          primes+2          overlapping pairs of primes
                                            [[2, 3], [3, 5], [5, 7], ...]
    {v:             }from                   select prime pairs `v = [a, b]`...
       (-)over v                            ...where `a` - `b`...
                <=-x                        is <= `x`
   (                              )@0@0     select the first element of the first pair

APL (NARS), 36 Zeichen, 72 Byte

∇r←h w;k
r←2
→0×⍳w≤r-⍨k←1πr⋄r←k⋄→2
∇

1π ist die Funktion "nächste Primzahl"; Prüfung:

  h¨1 2 3 4 6 10 16 17 18 30 50 100 200
2 3 7 7 23 113 523 523 523 1327 19609 370261 20831323