Gib die n-te Primzahl aus, die n enthält

39

Diese Frage wird eine Wendung beim Finden der nth Primzahl sein.

Herausforderung

Sie müssen ein Programm schreiben, das eine Eingabe benötigt n, und die ndritte Primzahl ausgeben, deren Dezimalrepräsentation die Dezimalrepräsentation von nals Unterzeichenfolge enthält.

Verwirrt? Hier sind einige Beispiele.

n=1
Primes: 2, 3, 5, 7, 11
                    ^1 first prime that contains a 1
Output: 11

n=2
Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23
        ^1                          ^2 second prime that contains a 2
Output: 23

n=3
Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23
           ^1           ^2          ^3 third prime that contains a 3
Output: 23

n=10
Primes: 2, 3, 5, 7, 11, ..., 97, 101, 103, 107, 109, ..., 997, 1009, 1013, 1019, 1021, 1031, 1033
                                 ^1   ^2   ^3   ^4             ^5    ^6    ^7    ^8    ^9    ^10 tenth prime that contains a 10
Output: 1033

Dies ist , daher gewinnt die niedrigste Bytezahl.

Wenn etwas verwirrend ist, hinterlassen Sie bitte einen Kommentar.

ericw31415
quelle
2
Gibt es dafür einen OEIS? Es fühlt sich an wie es sein sollte
MayorMonty
@SpeedyNinja Nein, ich habe es schon überprüft.
Adnan
Related
Alex A.
1
Ich kann nicht glauben, dass dies auf Platz 5 der Hot Network QuestionsListe stand.
ericw31415
Eine ähnliche Sequenz
Nathan Merrill

Antworten:

12

05AB1E , 8 Bytes

Code:

µN¹åNp*½

Erläuterung:

µ          # Run this until the counting variable has reached the input value.
 N¹å       # Check if the input number is in the range variable.
    Np     # Check if the range variable is prime.
      *    # Multiply those two numbers (which is basically an AND operator).
       ½   # If true, increment the counting variable.
           # After the loop, the stack is empty and implicitly prints N.

Verwendet CP-1252- Codierung. Probieren Sie es online! .

Adnan
quelle
10

Pyth - 11 Bytes

e.f&P_Z}`Q`

Test Suite .

Maltysen
quelle
8

Python 2, 67 65 62 Bytes

f=lambda n,k=0,m=2,p=1:k/n or-~f(n,k+p%m*(`n`in`m`),m+1,p*m*m)

Teste es auf Ideone .

Wie es funktioniert

Wir verwenden eine Folgerung aus dem Satz von Wilson :

Folgerung aus Wilsons Satz

Die Variable p ist immer gleich dem Quadrat der Fakultät von m - 1 .

Wenn k <n , k/nergibt sich 0 und f wird rekursiv aufgerufen. m wird inkrementiert, p wird aktualisiert und k wird nur dann inkrementiert, wenn m eine Primzahl ist, die n enthält .

Letzteres wird durch Addition des Ergebnisses von p%m*(`n`in`m`)zu k erreicht . Durch die logische Folge des Satzes von Wilson , wenn m prim ist , p%mkehrt 1 , und wenn nicht, gibt sie 0 .

Sobald k n erreicht , haben wir q gefunden , die n- te Primzahl, die n enthält .

Wir sind beim nächsten Aufruf während der Prüfung, also m = q + 1 . k/ngibt 1 zurück und die bitweisen Operatoren -~erhöhen diese Zahl einmal für jeden Funktionsaufruf. Da es dauert q - 1 Anruf f zu inkrementieren m von 2 bis q + 1 , der outmost Aufruf f kehrt 1 + q - 1 = q , wie beabsichtigt.

Dennis
quelle
6

Bash, 27 Bytes

primes 0|grep $1|sed $1q\;d

primes kommt von bsdgames.

Nimmt Eingaben als Befehlszeilenargument und gibt sie auf STDOUT aus.

Türknauf
quelle
4

Mathematica, 75 Bytes

Nest[NestWhile[b=NextPrime,b@#,!StringContainsQ@@ToString/@{#,a}&]&,1,a=#]&

Kann noch Golf sein.

LegionMammal978
quelle
Dies ist wahrscheinlich die schnellste Lösung, da NextPrime verwendet wird :)
4

Java, 194 180 173 171 112 Bytes

Code:

a->{int i=1,j,n,r=0;for(j=n=new Integer(a);(r+=++i>=j&(""+j).contains(""+n)?1:0)!=n;j+=j%i==0?i=1:0);return j;}

Ungolfed:

class P{
    static int i=1,j,n,r;
    public static void main(String[]s) {
        for(
                j=n=new Integer(s[0]); //executes once before first iteration
                (r+=++i>=j&(""+j).contains(""+n)?1:0)!=n; //executes on first and every iteration
                j+=j%i==0?i=1:0 //executes after first and every iteration
           ) {
            ;
        }
        System.out.print(j);
    }
}
Hoffentlich hilfreich
quelle
Hallo, willkommen bei PPCG! Zwei Dinge zu beachten, 1. Sie können zwei Leerzeichen bei P {und entfernen String[] s. Und 2. Sie geben derzeit nur die Ausgabe für 10, aber die Code-Golf-Herausforderung bestand darin, eine Eingabe zu nehmen nund die richtige Ausgabe basierend auf dieser Eingabe zu geben. Das könnte Sie auch interessieren: Tipps zum Golfen in Java.
Kevin Cruijssen
3

Ruby, 62 61 Bytes

->i{Prime.lazy.map(&:to_s).grep(/#{i}/).first(i)[-1]}

Benötigt das -rprimeFlag (+8 Bytes).

->i{            # lambda with one argument
Prime           # iterator over all primes
.lazy           # make the iterator lazy (can't evaluate infinite primes)
.map(&:x.to_s)  # convert the primes to strings
.grep(/#{i}/)   # find primes that regex match on the input (contain it)
.first(i)       # take the first (input) primes that satisfy this
[-1]            # take the last of those
}
Türknauf
quelle
3

MATL , 18 Bytes

`@YqVGVXf?3M]NG<]&

Probieren Sie es online!

Erläuterung

Dies erzeugt Primzahlen in einer do...whileSchleife. Für jede Primzahl wird die Bedingung geprüft (und die Primzahl wird verbraucht). Wenn er zufrieden ist, wird diese Primzahl erneut auf den Stapel gelegt. Die Anzahl der Elemente im Stapel wird als Anzahl der gefundenen qualifizierenden Primzahlen verwendet. Wenn es genug davon gibt, wird das letzte angezeigt.

`         % Do...while
  @       %   Push iteration index, k. Starts at 1
  YqV     %   k-th prime. Convert to string
  GV      %   Push input, n. Convert to string
  Xf      %   Find string within another
  ?       %   If non-empty
    3M    %     Push k-th prime again (increase stack size by 1)
  ]       %   End if
  NG<     %   Is stack size less than input number? If so proceeed with
          %   a new iteration; else exit do...while loop
]         % End do...while
&         % Implicitly display only top number in the stack 
Luis Mendo
quelle
1

Bash + GNU-Coreutils, 66 Bytes

Im Gegensatz zur @ Doorknob-Lösung benötigt diese nur Dinge, die auf jedem GNU / Linux installiert sind:

for((n=2;;n++)){
[ `factor $n|wc -w` -eq 2 ]&&grep $1<<<$n&&exit
}
rexkogitans
quelle
seq 1e20|factor|grep -Po "(?<=: )\d*$2\d$"|sed $1q\;d
Digitales Trauma
@DigitalTrauma, mein Gehirn funktioniert nicht so ;-)
rexkogitans
Braucht es die Zeilenumbrüche?
ericw31415
Danach for((...)){muss ein Leerzeichen oder ein Zeilenumbruch vorhanden sein, damit es keine Rolle spielt. Vor dem Abschluss }muss eine ; oder eine neue Zeile stehen, daher spielt es auch keine Rolle.
rexkogitans
1

Perl 6 , 41 Bytes

->$n {grep({.is-prime&&/$n/},2..*)[$n-1]}

Erläuterung:

-> $n { # has one parameter
  grep(
    {
      .is-prime # check that it is prime
      &&        # and
      / $n /    # that it contains the argument in the "string"
    },
    2 .. *      # for all numbers starting with 2
  )[ $n - 1 ]   # only take the $n-th one
                # ( accounting for 0 based array access )
}

Prüfung:

#! /usr/bin/env perl6
use v6.c;
use Test;

my &prefix:<ℙ𝕟> = ->$n {grep({.is-prime&&/$n/},2..*)[$n-1]}

my @test = (
  1  => 11,
  2  => 23,
  3  => 23,
  10 => 1033,
);

plan +@test;

for @test {
  is ℙ𝕟.key, .value, .gist
}
1..4
ok 1 - 1 => 11
ok 2 - 2 => 23
ok 3 - 3 => 23
ok 4 - 10 => 1033
Brad Gilbert b2gills
quelle
1

Java 8, 192 183 181 171 Bytes (volles Programm)

interface M{static void main(String[]a){long n=new Long(a[0]),c=0,r=1,m,i;for(;c<n;c+=m>1&(r+"").contains(a[0])?1:0)for(m=++r,i=2;i<m;m=m%i++<1?0:m);System.out.print(r);}}

Probieren Sie es online aus.

Erläuterung:

interface M{                    // Class
  static void main(String[]a){  //  Mandatory main-method
    long n=new Long(a[0]),      //   Input argument as number
         c=0,                   //   Counter, starting at 0
         r=1,                   //   Result-number, starting at 1
         m,i;                   //   Temp number
    for(;c<n;                   //   Loop as long as `c` does not equals `n`
        c+=                     //     After every iteration: increase `c` by:
           m>1                  //      If the current `r` is a prime,
           &(r+"").contains(a[0])?
                                //      and this prime contains the input `n`
            1                   //       Increase `c` by 1
           :                    //      Else:
            0)                  //       Leave `c` the same
      for(m=++r,                //    Increase `r` by 1 first with `++r`, and set `m` to it
          i=2;i<m;              //    Inner loop `i` in the range [2, `m`)
        m=m%i++<1?              //     If `m` is divisible by `i`
           0                    //      Change `m` to 0 (so it's not a prime)
          :                     //     Else:
           m);                  //      Leave `m` unchanged
    System.out.print(r);}}      //    Print `r` as result

Java 8, 105 Bytes (Lambda-Funktion)

n->{int c=0,r=1,m,i;for(;c<n;c+=m>1&(r+"").contains(n+"")?1:0)for(m=++r,i=2;i<m;m=m%i++<1?0:m);return r;}

Probieren Sie es online aus.

Wie oben, aber mit nInteger-Eingabe und ohne die ausführlichen Klasseninhalte.

Kevin Cruijssen
quelle
1
Sie können &&mit Ihrem regulären Ausdruck ersetzen &und entfernen ?.
Cliffroot
@cliffroot Danke, habe den Beitrag bearbeitet. Ich vergesse immer &&und &aus irgendeinem Grund ..
Kevin Cruijssen
0

Clojure, 118 Bytes

(defn s[n](nth(filter(fn[x](if(.contains(str x)(str n))(not-any? #(=(mod x %)0)(range 2 x))))(drop 2(range)))(dec n)))

Erhält gerade das n-te Element einer faulen unendlichen Folge von Zahlen, die Primzahlen sind und nin ihrer Zeichenfolgendarstellung haben.

Sie können es hier ausprobieren: https://ideone.com/ioBJjt

Cliffroot
quelle
0

Eigentlich 16 Bytes

;$╗`P$╜@íu`╓dP.X

Probieren Sie es online!

Erläuterung:

;$╗`P$╜@íu`╓dP.X
;$╗               make a copy of n, push str(n) to reg0
   `      `╓      push the first n values where f(k) is truthy, starting with k=0:
    P$              kth prime, stringified
      ╜@íu          1-based index of n, 0 if not found
            d     remove last element of list and push it to the stack (dequeue)
             P    nth prime
              .   print
               X  discard rest of list
Mego
quelle
0

PowerShell v2 +, 108 bis 99 Byte

Ooof. Das Fehlen jeglicher eingebauter Primberechnung / -prüfung tut hier wirklich weh.

param($n)for(){for(;'1'*++$i-match'^(?!(..+)\1+$)..'){if("$i"-like"*$n*"){if(++$o-eq$n){$i;exit}}}}

Übernimmt die Eingabe $n, tritt in eine for()Endlosschleife ein. Bei jeder Iteration verwenden wir eine forSchleife, die um den PowerShell-Regex-Prime-Checker (h / t für Martin) gewickelt ist, um ihn durch Inkrementieren $ijedes Mal durch die Schleife in einen Prime-Generator zu verwandeln . (Wenn Sie beispielsweise nur ausführen , for(){for(;'1'*++$i-match'^(?!(..+)\1+$)..'){$i}}wird die Ausgabe 2, 3, 5, 7...durch Zeilenumbrüche getrennt).

Dann eine einfache -likeÜberprüfung, um zu sehen, ob $nsich irgendwo etwas in $iunserem Zähler befindet , und eine Erhöhung unseres Zählers $o. Wenn wir erreicht haben, wo $nund $ogleich sind, geben Sie $iund aus exit. Andernfalls fahren wir mit der forSuche nach der nächsten Primzahl fort und der Vorgang wiederholt sich.

AdmBorkBork
quelle
0

APL (NARS), 39 Zeichen, 78 Byte

{s←⍕w←⍵⋄2{(w≤⍵)∧k←∨/s⍷⍕⍺:⍺⋄(1π⍺)∇⍵+k}1}

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

  f←{s←⍕w←⍵⋄2{(w≤⍵)∧k←∨/s⍷⍕⍺:⍺⋄(1π⍺)∇⍵+k}1}
  f¨1 2 3 10
11 23 23 1033 

aber das geht schon bei 20 aus dem stapelplatz ... stattdessen scheint das unten ok zu sein auch wenn die länge etwas länger ist (61 zeichen)

∇r←f w;i;k;s
r←2⋄s←⍕w⋄i←1
→0×⍳(w≤i)∧k←∨/s⍷⍕r⋄r←1πr⋄i+←k⋄→2
∇

  f¨1 2 3 10 20 100
11 23 23 1033 4201 100999 
RosLuP
quelle