Geben Sie die nächstgelegene Primzahl zurück

33

Herausforderung

Dies ist ganz einfach: Geben Sie bei einer positiven Ganzzahl von bis zu 1.000.000 die nächste Primzahl zurück.

Wenn die Zahl selbst eine Primzahl ist, sollten Sie diese Zahl zurückgeben. Wenn es zwei Primzahlen gibt, die der angegebenen Zahl gleich sind, geben Sie die niedrigere der beiden zurück.

Die Eingabe erfolgt in Form einer einzelnen Ganzzahl, und die Ausgabe sollte auch in Form einer Ganzzahl erfolgen.

Es ist mir egal, wie Sie die Eingabe (Funktion, STDIN usw.) einlesen oder die Ausgabe (Funktion, STDOUT usw.) anzeigen, solange dies funktioniert.

Dies ist Codegolf, daher gelten die Standardregeln - das Programm mit den wenigsten Bytes gewinnt!

Testfälle

Input  =>  Output
------    -------
80     =>      79
100    =>     101
5      =>       5
9      =>       7
532    =>     523
1      =>       2
Nathan Dimmer
quelle
5
Hallo und willkommen bei PPCG !. Um Abstimmungen aufgrund mangelnder Qualität zu vermeiden, schlage ich vor, sie zuerst in den Sandkasten zu stellen und sie nach ein paar Tagen hier zu veröffentlichen
Luis felipe De jesus Munoz
Dies ist eine der in dieser Herausforderung angeforderten Ausgaben .
Arnauld
Sehr eng verwandt, aber nicht ganz identisch.
Giuseppe
@Arnauld Ich habe das gesehen, aber ich dachte, dass sie unterschiedlich genug sind, um eine neue Frage zu rechtfertigen.
Nathan Dimmer
2
Siehe auch OEIS A051697 .
Eric Towers

Antworten:

9

Gaia , 3 Bytes

ṅD⌡

Probieren Sie es online!

Ziemlich langsam für große Eingaben, funktioniert aber bei genügend Arbeitsspeicher / Zeit.

Ich bin mir nicht sicher, warum D⌡implizit noch einmal drängt z, aber das macht dies zu einer bemerkenswert kurzen Antwort!

ṅ	| implicit input z: push first z prime numbers, call it P
 D⌡	| take the absolute difference between P and (implicit) z,
	| returning the smallest value in P with the minimum absolute difference
Giuseppe
quelle
13

JavaScript (ES6), 53 Byte

n=>(g=(o,d=N=n+o)=>N%--d?g(o,d):d-1?g(o<0?-o:~o):N)``

Probieren Sie es online!

Kommentiert

n => (            // n = input
  g = (           // g = recursive function taking:
    o,            //   o = offset
    d =           //   d = current divisor, initialized to N
    N = n + o     //   N = input + offset
  ) =>            //
    N % --d ?     // decrement d; if d is not a divisor of N:
      g(o, d)     //   do recursive calls until it is
    :             // else:
      d - 1 ?     //   if d is not equal to 1 (either N is composite or N = 1):
        g(        //     do a recursive call with the next offset:
          o < 0 ? //       if o is negative:
            -o    //         make it positive (e.g. -1 -> +1)
          :       //       else:
            ~o    //         use -(o + 1) (e.g. +1 -> -2)
        )         //     end of recursive call
      :           //   else (N is prime):
        N         //     stop recursion and return N
)``               // initial call to g with o = [''] (zero-ish)
Arnauld
quelle
10

05AB1E , 5 Bytes

Åps.x

Probieren Sie es online! oder als Testsuite

Ineffizient für große Zahlen

Emigna
quelle
3
Schade Ånist " Im Falle eines Unentschieden wird die höhere Primzahl gedrückt ".
Kevin Cruijssen
@ KevinCruijssen: Weder habe ich bis jetzt :)
Emigna
7

Oktave , 40 Bytes

@(n)p([~,k]=min(abs(n-(p=primes(2*n)))))

Probieren Sie es online!

Dies beruht auf der Tatsache, dass zwischen nund immer eine Primzahl steht 2*n( Bertrand-Chebyshev-Theorem ).

Wie es funktioniert

@(n)p([~,k]=min(abs(n-(p=primes(2*n)))))

@(n)                                      % Define anonymous function with input n
                       p=primes(2*n)      % Vector of primes up to 2*n. Assign to p
                abs(n-(             ))    % Absolute difference between n and each prime
      [~,k]=min(                      )   % Index of first minimum (assign to k; not used)
    p(                                 )  % Apply that index to p
Luis Mendo
quelle
5

Wolfram Language (Mathematica) , 31 Byte

Nearest[Prime~Array~78499,#,1]&

Probieren Sie es online!

                              & (*pure function*)
        Prime~Array~78499       (*among the (ascending) first 78499 primes*)
                            1   (*select one*)
Nearest[                 ,#, ]  (*which is nearest to the argument*)

1000003 ist die 78499. Primzahl. Nearestpriorisiert Werte, die früher in der Liste erscheinen (die niedriger sind).

attinat
quelle
5
Nearest[Prime@Range@#,#,1]&für 27
Ben
5

Brachylog , 7 5 Bytes

;I≜-ṗ

Probieren Sie es online!

2 Bytes gespart dank @DLosc.

Erläuterung

;I≜      Label an unknown integer I (tries 0, then 1, then -1, then 2, etc.)
   -     Subtract I from the input
    ṗ    The result must be prime
Tödlich
quelle
@ DLosc Meistens weil ich blöd bin. Vielen Dank.
Fatalize
Ich denke, wir sind es gerade aus verschiedenen Richtungen angegangen. Ich nehme an, Sie haben von Anfang an darüber nachgedacht, während ich über das Pairing und Subtrahieren nachgedacht habe und erst später festgestellt habe, dass ich dafür sorgen muss , dass es funktioniert. :)
DLosc
4

Pyth, 10 Bytes

haDQfP_TSy

Versuchen Sie es online hier oder überprüfen alle Testfälle auf einmal hier .

haDQfP_TSyQ   Implicit: Q=eval(input())
              Trailing Q inferred
         yQ   2 * Q
        S     Range from 1 to the above
    f         Filter keep the elements of the above, as T, where:
     P_T        Is T prime?
  D           Order the above by...
 a Q          ... absolute difference between each element and Q
                This is a stable sort, so smaller primes will be sorted before larger ones if difference is the same
h             Take the first element of the above, implicit print
Sok
quelle
4

Gelee , 9 7 Bytes

ḤÆRạÞµḢ

Probieren Sie es online!

Langsam für größere Eingaben, funktioniert aber für den angeforderten Bereich. Vielen Dank an @EriktheOutgolfer für das Speichern von 2 Bytes!

Nick Kennedy
quelle
Hey, das ist schlau! Sparen Sie zwei durch Ersetzen _A¥mit (absolute Differenz). Oh, und das kann wirklich sein .
Erik der Outgolfer
@EriktheOutgolfer danke. Sicherlich funktioniert die Verwendung nicht immer? Dies bedeutet, dass nur Primzahlen bis zu n + 1 gefunden werden, während die nächstliegende n + 2 sein kann.
Nick Kennedy
Hm, das ist ein Problem.
Erik der Outgolfer
4

Python 2 , 71 Bytes

f=lambda n,k=1,p=1:k<n*3and min(k+n-p%k*2*n,f(n,k+1,p*k*k)-n,key=abs)+n

Probieren Sie es online!

p(k-1)!2p%kabs(k-n)kk-nabsnk

Der Ausdruck k+n-p%k*2*nist so konzipiert, dass k-ner Primzahlen (wo p%k=1) angibt , andernfalls ist ein "schlechter" Wert von k+nimmer größer als der absolute Wert und hat keinen Einfluss auf das Minimum, sodass Nicht-Primzahlen übergangen werden.

xnor
quelle
4

C (GCC) , 87 76 74 72 Byte

Optimierung von innat3s C # (Visual C # Interactive Compiler), 100 Bytes

f(n,i,t,r,m){for(t=0,m=n;r-2;t++)for(r=i=1,n+=n<m?t:-t;i<n;n%++i||r++);}

Probieren Sie es online!

Natural Number Guy
quelle
Hallo und willkommen bei PPCG. Ein paar Tipps: r!=2Entspricht r-2, n%++i?0:r++kann höchstwahrscheinlich sein n%++i||r++.
Jonathan Frech
Das habe ich nicht sofort gesehen. Vielen Dank.
Natural Number Guy
3

Ordentlich , 43 Bytes

{x:(prime↦splice(]x,-1,-∞],[x,∞]))@0}

Probieren Sie es online!

Erläuterung

Dies ist ein Lambda mit Parameter x. Dies funktioniert durch Erstellen der folgenden Sequenz:

[x - 1, x, x - 2, x + 1, x - 3, x + 2, x - 4, x + 3, ...]

Dies verbindet die beiden Sequenzen ]x, -1, -∞](links geschlossen, rechts offen) und [x, ∞](beide offen).

Denn x = 80das sieht so aus:

[79, 80, 78, 81, 77, 82, 76, 83, 75, 84, 74, 85, ...]

Dann verwenden wir f↦s, um alle Elemente aus der sBefriedigung auszuwählen f. In diesem Fall werden alle zusammengesetzten Zahlen herausgefiltert, wobei nur die Primzahlen übrig bleiben. Für das gleiche xwird dies:

[79, 83, 73, 71, 89, 67, 97, 61, 59, 101, 103, 53, ...]

Dann verwenden wir (...)@0, um das erste Mitglied dieser Sequenz auszuwählen. Da die niedrigere der beiden ausgewählt werden muss, wird die Sequenz, die mit beginnt, x - 1zuerst eingespleißt.

Hinweis: Nur eines von xund x - 1kann eine Primzahl sein, daher ist es in Ordnung, dass die gespleißte Sequenz mit beginnt x - 1. Obwohl die Sequenz auf beiden Seiten offen sein könnte ( [x,-1,-∞]), würde dies unnötigerweise xzweimal in die Sequenz einschließen . Aus Gründen der "Effizienz" habe ich mich für die links geschlossene Version entschieden (auch, weil ich Tidy gerne zur Schau stelle).

Conor O'Brien
quelle
3

Faktor 91 Bytes

: p ( x -- x ) [ nprimes ] keep dupd [ - abs ] curry map swap zip natural-sort first last ;

Probieren Sie es online!

Galen Ivanov
quelle
3

APL (Dyalog ausgefahren) , 20 15 Bytes SBCS

Tacit-Präfix-Funktion, inspiriert von Galen Ivanovs J-Antwort .

⊢(⊃⍋⍤|⍤-⊇⊢)¯2⍭⍳

Probieren Sie es online!

Ermittelt einen durch das Argument.

¯2⍭ n-te Primzahlen davon

⊢() Wende die folgende implizite Funktion an, wobei das ursprüngliche Argument das linke Argument ist:

 die Primzahlen

 indiziert von:

   die aufsteigende Grad (Indizes , die aufsteigend sortieren würde)
   von
  | der Größe (Absolutwert)
   von
  - den Unterschieden

 wähle den ersten (dh den mit dem kleinsten Unterschied)

Adam
quelle
3

Perl 6 , 35 Bytes

{$_+=($*=-1)*$++until .is-prime;$_}

Probieren Sie es online!

Dies verwendet die Veitcel-Technik zum Erzeugen der Liste 0, -1, 2, -3, vereinfacht diese jedoch erheblich, ($*=-1)*$++indem die in P6 verfügbaren anonymen Statusvariablen verwendet werden (ich hatte sie ursprünglich -1 ** $++ * $++, aber beim Golfen verliert das Negative den Vorrang). Es gibt einen eingebauten Prime Checker, aber leider untilverhindert der den automatisch zurückgegebenen Wert, so dass es ein zusätzliches Herumhängen gibt $_.

user0721090601
quelle
Normalerweise würde ich einen Sequenzoperator-Ansatz für so etwas verwenden, der aber ein Byte länger ausfällt, was eine gute Arbeit ist, eine kürzere Methode zu finden
Jo King,
@JoKing guten Fang. Die Dinge, die passieren, wenn ich zu schnell Golf spiele, nachdem ich eine funktionierende Lösung gefunden habe. Ich hatte eine ähnliche, aber der verdammte Mangel an [-1] haha
user0721090601
3

C, 122 121 104 Bytes

p(a,i){for(i=1;++i<a;)if(a%i<1)return 0;return a>1;}c(a,b){for(b=a;;b++)if(p(--a)|p(b))return p(b)?b:a;}

Verwenden Sie die aufrufende Funktion c()und übergeben Sie die Nummer als Argument. Es sollte die nächste Primzahl zurückgeben.

Dank Verkörperung der Ignoranz für 1 Byte konnte eine große Verbesserung erzielt werden.

Probieren Sie es online!

Lince Assassino
quelle
Aber c()erhält zwei Parameter ... Auch können Sie wahrscheinlich die Verkürzung while(1)auf for(;;)(nicht getestet, da ich nicht bekommen , wie Sie Ihren Code auszuführen
Verkörperung der Ignoranz
@EmbodimentofIgnorance Ich habe es geschrieben und alles auf einem Online-C-Compiler getestet. Ich konnte c()nur die Übergabe des ersten Parameters aufrufen . Und Sie haben Recht, for(;;)spart mir ein Byte, nur noch 117 übrig, um den ersten Platz zu erreichen :)
Lince Assassino
110 Bytes #define r return p(a,i){i=1;while(++i<a)if(a%i<1)r 0;r a>1;}c(a,b){b=a;for(;;b++){if(p(--a))r a;if(p(b))r b;}}. Hier ist ein TIO-Link: tio.run/…
Verkörperung der Ignoranz
106: tio.run/…
Verkörperung der Ignoranz
101: tio.run/…
Verkörperung der Ignoranz
3

Wolfram Language (Mathematica) , 52 Byte

If[PrimeQ[s=#],s,#&@@Nearest[s~NextPrime~{-1,1},s]]&

Probieren Sie es online!

J42161217
quelle
Sie haben einen zusätzlichen Speicherplatz, der entfernt werden kann, um ein Byte zu speichern.
Ben
@Ben du hast recht. Danke
J42161217
2

APL (NARS), 38 Zeichen, 76 Byte

{⍵≤1:2⋄0π⍵:⍵⋄d←1π⍵⋄(d-⍵)≥⍵-s←¯1π⍵:s⋄d}

0π ist der Test für Primzahl, ¯1π die vorherige Primzahl, 1π ist die nächste Primzahl; Prüfung:

  f←{⍵≤1:2⋄0π⍵:⍵⋄d←1π⍵⋄(d-⍵)≥⍵-s←¯1π⍵:s⋄d}
  f¨80 100 5 9 532 1
79 101 5 7 523 2 
RosLuP
quelle
2

Perl 5 , 59 Bytes

$a=0;while((1x$_)=~/^.?$|^(..+?)\1+$/){$_+=(-1)**$a*($a++)}

Probieren Sie es online!

/^.?$|^(..+?)\1+$/ ist knifflig, um Prime zu überprüfen

(-1)**$a*($a++) Folge 0, -1, 2, -3 erzeugen ...

Veitcel
quelle
2

MathGolf , 10 Bytes

∞╒g¶áÅ-±├Þ

Probieren Sie es online aus.

Erläuterung:

            # Double the (implicit) input-integer
            # Create a list in the range [1, 2*n]
  g         # Filter so only the prime numbers remain
    áÅ       # Sort this list using the next two character:
           #  The absolute difference with the (implicit) input-integer
            # Push the first item of the list
             # (unfortunately without popping the list itself, so:)
         Þ   # Discard everything from the stack except for the top
             # (which is output implicitly as result)
Kevin Cruijssen
quelle
@JoKing Danke! Ich wusste, dass Max darüber nachdachte, es zu ändern, wusste aber nicht, dass er es tatsächlich tat. In den Dokumenten wird immer noch die alte angegeben.
Kevin Cruijssen
Ah, ich verwende die Datei mathgolf.txt als Referenz, da sie aktueller zu sein scheint
Jo King,
@JoKing Ja, er hat mir gestern auch von dieser Datei erzählt. Wird es von nun an verwenden. :)
Kevin Cruijssen
2

Python 2 (Cython) , 96 Bytes

l=lambda p:min(filter(lambda p:all(p%n for n in range(2,p)),range(2,p*3)),key=lambda x:abs(x-p))

Probieren Sie es online!

Snaddyvitch Spender
quelle
Könnte in der Lage sein, ein paar Bytes überr=range;...
Skyler
1
@ Arnauld, es funktioniert jetzt für x = 1
Snaddyvitch Dispenser
2

C # (Visual C # Interactive Compiler) , 104 100 Byte

n=>{int r=0,t=0,m=n;while(r!=2){n+=(n<m)?t:-t;t++;r=0;for(int i=1;i<=n;i++)if(n%i==0)r++;}return n;}

Probieren Sie es online!

Erläuterung:

int f(int n)
{
    int r = 0; //stores the amount of factors of "n"
    int t = 0; //increment used to cover all the integers surrounding "n"
    int m = n; //placeholder to toggle between adding or substracting "t" to "n"

    while (r != 2) //while the amount of factors found for "n" is different to 2 ("1" + itself)
    {
        n += (n < m) ? t : -t; //increment/decrement "n" by "t" (-0, -1, +2, -3, +4, -5,...)
        t++;
        r = 0;
        for (int i = 1; i <= n; i++) //foreach number between "1" and "n" increment "r" if the remainder of its division with "n" is 0 (thus being a factor)
            if (n % i == 0) r++; 
    }
    return n;
}

Console.WriteLine(f(80)); //79
Innat3
quelle
2

Java 8, 88 87 Bytes

n->{for(int c=0,s=0,d,N=n;c!=2;s++)for(c=d=1,n+=n<N?s:-s;d<n;)if(n%++d<1)c++;return n;}

Port of @NaturalNumberGuys (erste) C-Antwort , also stelle sicher, dass du ihn positiv bewertest !!
-1 Byte danke an @ OlivierGrégoire .

Probieren Sie es online aus.

Erläuterung:

n->{               // Method with integer as both parameter and return-type
  for(int c=0,     //  Counter-integer, starting at 0
          s=0,     //  Step-integer, starting at 0 as well
          d,       //  Divisor-integer, uninitialized
          N=n;     //  Copy of the input-integer
      c!=2;        //  Loop as long as the counter is not exactly 2 yet:
      s++)         //    After every iteration: increase the step-integer by 1
    for(c=d=1,     //   (Re)set both the counter and divisor to 1
        n+=n<N?    //   If the input is smaller than the input-copy:
            s      //    Increase the input by the step-integer
           :       //   Else:
            -s;    //    Decrease the input by the step-integer
        d<n;)      //   Inner loop as long as the divisor is smaller than the input
      if(n%++d     //    Increase the divisor by 1 first with `++d`
              <1)  //    And if the input is evenly divisible by the divisor:
        c++;       //     Increase the counter-integer by 1
  return n;}       //  Return the now modified input-integer as result
Kevin Cruijssen
quelle
2

Java (JDK) , 103 Byte

n->{int p=0,x=0,z=n,d;for(;p<1;p=p>0?z:0,z=z==n+x?n-++x:z+1)for(p=z/2,d=1;++d<z;)p=z%d<1?0:p;return p;}

Probieren Sie es online!

Olivier Grégoire
quelle
Ähm .. ich hatte schon einen Port für seine Antwort angelegt .. ;) Obwohl deins 1 Byte kürzer ist, ist doch etwas anderes. EDIT: Ah, ich habe eine Ergebnis-Ganzzahl außerhalb der Schleife, und Sie ändern die Eingabe innerhalb der Schleife, daher das -1-Byte für ;. :) Soll ich meine Antwort löschen? .. Fühlen Sie sich frei, die Erklärung zu kopieren.
Kevin Cruijssen
@KevinCruijssen Ups, rollbacked!
Olivier Grégoire
Entschuldigung (und danke für das -1 Byte). Ich mag aber auch deine Version. Bereits aufgewertet, bevor ich die Antwort von NaturalNumberGuy sah.
Kevin Cruijssen
2

Haskell , 79 74 Bytes (danke an Laikoni)

72 Bytes als Annonymus-Funktion (das anfängliche "f =" könnte in diesem Fall entfernt werden).

f=(!)(-1);n!x|x>1,all((>0).mod x)[2..x-1]=x|y<-x+n=last(-n+1:[-n-1|n>0])!y

Probieren Sie es online!


ursprünglicher Code:

f=(!)(-1);n!x|x>1&&all((>0).mod x)[2..x-1]=x|1>0=(last$(-n+1):[-n-1|n>0])!(x+n)

Probieren Sie es online!

Erläuterung:

f x = (-1)!x

isPrime x = x > 1 && all (\k -> x `mod` k /= 0)[2..x-1]
n!x | isPrime x = x            -- return the first prime found
    | n>0       = (-n-1)!(x+n) -- x is no prime, continue with x+n where n takes the 
    | otherwise = (-n+1)!(x+n) -- values -1,2,-3,4 .. in subsequent calls of (!)
Sachera
quelle
1
Innerhalb einer Wache können Sie ,anstelle von verwenden &&. (last$ ...)kann sein last(...), und der zweite Schutz 1>0kann für eine Bindung verwendet werden, um Klammern zu speichern, z y<-x+n.
Laikoni
Anonyme Funktionen sind im Allgemeinen zulässig, sodass die Initiale f=nicht gezählt werden muss. Auch die Klammer, die einschließt, (-1+n)kann fallengelassen werden.
Laikoni,
Danke für die Vorschläge. Ich wusste nicht "," und Bindungen sind in Funktionswächtern erlaubt! Aber ich mag die Idee einer anonymen Funktion als Antwort nicht wirklich. Meiner Meinung nach fühlt es sich nicht richtig an.
Sachera
Weitere Tipps finden Sie in unserer Sammlung von Tipps zum Golfen in Haskell . Es gibt auch eine Anleitung zu den Golfregeln in Haskell und einen speziellen Chatraum: Von Monaden und Männern .
Laikoni
2

VDM-SL , 161 Bytes

f(i)==(lambda p:set of nat1&let z in set p be st forall m in set p&abs(m-i)>=abs(z-i)in z)({x|x in set{1,...,9**7}&forall y in set{2,...,1003}&y<>x=>x mod y<>0})

Ein vollständiges auszuführendes Programm könnte so aussehen - es ist erwähnenswert, dass die Grenzen der verwendeten Primzahlenmenge wahrscheinlich geändert werden sollten, wenn Sie dies tatsächlich ausführen möchten, da es lange dauern wird, bis 1 Million ausgeführt werden:

functions
f:nat1+>nat1
f(i)==(lambda p:set of nat1&let z in set p be st forall m in set p&abs(m-i)>=abs(z-i)in z)({x|x in set{1,...,9**7}&forall y in set{2,...,1003}&y<>x=>x mod y<>0})

Erläuterung:

f(i)==                                        /* f is a function which takes a nat1 (natural number not including 0)*/
(lambda p:set of nat1                         /* define a lambda which takes a set of nat1*/
&let z in set p be st                         /* which has an element z in the set such that */
forall m in set p                             /* for every element in the set*/
&abs(m-i)                                     /* the difference between the element m and the input*/
>=abs(z-i)                                    /* is greater than or equal to the difference between the element z and the input */
in z)                                         /* and return z from the lambda */
(                                             /* apply this lambda to... */
{                                             /* a set defined by comprehension as.. */
x|                                            /* all elements x such that.. */ 
x in set{1,...,9**7}                          /* x is between 1 and 9^7 */
&forall y in set{2,...,1003}                  /* and for all values between 2 and 1003*/
&y<>x=>x mod y<>0                             /* y is not x implies x is not divisible by y*/
} 
)
Abgelaufene Daten
quelle
1

C # (Visual C # Interactive Compiler) , 112 Byte

g=>Enumerable.Range(2,2<<20).Where(x=>Enumerable.Range(1,x).Count(y=>x%y<1)<3).OrderBy(x=>Math.Abs(x-g)).First()

Probieren Sie es online!

Der linke Bereich wird bei der Übermittlung um 20, bei TIO jedoch um 10 verschoben, sodass TIO für Testfälle beendet wird.

Abgelaufene Daten
quelle