Wydrukuj n-tą liczbę pierwszą zawierającą n

39

To pytanie będzie niespodzianką w znalezieniu nczwartej liczby pierwszej.

Wyzwanie

Musisz napisać program, który pobierze jedno dane wejściowe ni wyświetli npierwszą liczbę pierwszą, której reprezentacja dziesiętna zawiera dziesiętną reprezentację njako podtekst.

Zmieszany? Oto kilka przykładów.

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

To jest , więc wygrywa najmniejsza liczba bajtów.

Jeśli coś jest mylące, zostaw komentarz.

ericw31415
źródło
2
Czy jest na to OEIS? Wydaje się, że powinien być
MayorMonty
@SpeedyNinja Nie, już sprawdziłem.
Adnan
Powiązane
Alex A.
1
Nie mogę uwierzyć, że dzięki temu znalazł się na 5 miejscu na Hot Network Questionsliście.
ericw31415
Podobna sekwencja
Nathan Merrill

Odpowiedzi:

12

05AB1E , 8 bajtów

Kod:

µN¹åNp*½

Wyjaśnienie:

µ          # 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.

Wykorzystuje kodowanie CP-1252 . Wypróbuj online! .

Adnan
źródło
10

Pyth - 11 bajtów

e.f&P_Z}`Q`

Pakiet testowy .

Maltysen
źródło
8

Python 2, 67 65 62 bajtów

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)

Przetestuj na Ideone .

Jak to działa

Używamy następstwa twierdzenia Wilsona :

następstwo twierdzenia Wilsona

Przez cały czas zmienna p jest równa kwadratowi silni m - 1 .

Jeśli k <n , k/nda 0, a f jest wywoływane rekurencyjnie. m jest zwiększane, p jest aktualizowane, a k jest zwiększane tylko wtedy, gdy m jest liczbą pierwszą zawierającą n .

To ostatnie osiąga się przez dodanie wyniku p%m*(`n`in`m`)do k . Zgodnie z twierdzeniem Wilsona, jeśli m jest liczbą pierwszą, p%mzwraca 1 , a jeśli nie, zwraca 0 .

Gdy k osiągnie n , znaleźliśmy q , n- ta liczba pierwsza zawierająca n .

Jesteśmy w trakcie następnego połączenia podczas sprawdzania, więc m = q + 1 . k/nzwróci 1 , a operatorzy bitowi -~zwiększą ten numer jeden raz dla każdego wywołania funkcji. Ponieważ potrzeba q - 1 wywołań do f, aby zwiększyć m od 2 do q + 1 , najbardziej zewnętrzne wywołanie do f zwróci 1 + q - 1 = q , zgodnie z przeznaczeniem.

Dennis
źródło
6

Bash, 27 bajtów

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

primes pochodzi z bsdgames.

Pobiera dane wejściowe jako argument wiersza poleceń i wyświetla dane wyjściowe w STDOUT.

Klamka
źródło
4

Mathematica, 75 bajtów

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

Nadal można grać w golfa.

LegionMammal978
źródło
Jest to prawdopodobnie najszybsze rozwiązanie, ponieważ korzysta z NextPrime :)
4

Java, 194 180 173 171 112 bajtów

Kod:

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

Nie golfowany:

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);
    }
}
Mam nadzieję, że jest pomocna
źródło
Cześć, witamy w PPCG! Dwie rzeczy do zapamiętania: 1. Możesz usunąć dwa spacje w P {i String[] s. I 2. obecnie podajesz tylko dane wyjściowe 10, ale wyzwaniem dla gry w golfa było wzięcie danych wejściowych ni podanie odpowiednich danych wyjściowych na podstawie tych danych wejściowych. Może Cię to zainteresować: Wskazówki dotyczące gry w golfa w Javie.
Kevin Cruijssen
3

Rubin, 62 61 bajtów

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

Wymaga -rprimeflagi (+8 bajtów).

->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
}
Klamka
źródło
3

MATL , 18 bajtów

`@YqVGVXf?3M]NG<]&

Wypróbuj online!

Wyjaśnienie

To generuje liczby pierwsze w kolejności za pomocą do...whilepętli. Dla każdej liczby pierwszej testowany jest warunek (i liczba pierwsza jest konsumowana). Jeśli jest spełniony, ta liczba pierwsza jest ponownie umieszczana na stosie. Liczba elementów na stosie jest używana do zliczenia liczby kwalifikujących liczb pierwszych, które znaleźliśmy. Gdy jest ich wystarczająco dużo, wyświetlana jest ostatnia.

`         % 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
źródło
1

Bash + GNU coreutils, 66 bajtów

W przeciwieństwie do rozwiązania @ Doorknob, ten potrzebuje tylko rzeczy, które są zainstalowane na każdym systemie GNU / Linux:

for((n=2;;n++)){
[ `factor $n|wc -w` -eq 2 ]&&grep $1<<<$n&&exit
}
rexkogitans
źródło
seq 1e20|factor|grep -Po "(?<=: )\d*$2\d$"|sed $1q\;d
Cyfrowa trauma
@DigitalTrauma, mój mózg nie działa w ten sposób ;-)
rexkogitans
Czy potrzebuje nowych linii?
ericw31415
Po for((...)){tym musi być spacja lub znak nowej linii, więc nie ma to znaczenia. Przed zamknięciem }musi być ; znak nowej linii, więc to też nie ma znaczenia.
rexkogitans
1

Perl 6 , 41 bajtów

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

Wyjaśnienie:

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

Test:

#! /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
źródło
1

Java 8, 192 183 181 171 bajtów (pełny program)

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

Wypróbuj online.

Wyjaśnienie:

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 bajtów (funkcja lambda)

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

Wypróbuj online.

To samo co powyżej, ale z nwejściem całkowitym i bez pełnych informacji o klasie.

Kevin Cruijssen
źródło
1
można zastąpić &&z &i usunąć ?z regexp.
Cliffroot
@cliffroot Dzięki, edytowałem post. Zawsze zapominam &&i &z jakiegoś powodu ..
Kevin Cruijssen
0

Clojure, 118 bajtów

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

Po prostu dostaje n-ty element leniwej, nieskończonej sekwencji liczb, które są liczbą pierwszą i mają nw swojej reprezentacji łańcuchowej.

Możesz spróbować tutaj: https://ideone.com/ioBJjt

Cliffroot
źródło
0

Właściwie 16 bajtów

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

Wypróbuj online!

Wyjaśnienie:

;$╗`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
źródło
0

PowerShell v2 +, 108 99 bajtów

O nie. Brak jakiegokolwiek wbudowanego obliczania / sprawdzania liczb pierwszych naprawdę tutaj boli.

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

Pobiera dane wejściowe $n, wchodzi w nieskończoną for()pętlę. W każdej iteracji używamy forpętli owiniętej wokół sprawdzania liczb regularnych wyrażeń regularnych PowerShell (h / t do Martina), aby przekształcić ją w generator liczb pierwszych, zwiększając za $ikażdym razem pętlę. (Na przykład, uruchomienie właśnie for(){for(;'1'*++$i-match'^(?!(..+)\1+$)..'){$i}}spowoduje wyjście 2, 3, 5, 7...oddzielone znakami nowej linii).

Następnie wystarczy -likesprawdzić, czy $ngdzieś jest $i, i zwiększyć nasz licznik $o. Jeśli osiągnęliśmy, gdzie $ni $ojesteśmy równi, wydajność $ii exit. W przeciwnym razie przejdziemy dalej, foraby znaleźć następną liczbę pierwszą, a proces się powtórzy.

AdmBorkBork
źródło
0

APL (NARS), 39 znaków, 78 bajtów

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

1π jest następną liczbą pierwszą ...; test:

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

ale to już przy 20 wychodzi z miejsca na stosie ... Zamiast tego wydaje się to w porządku, nawet jeśli ma trochę więcej długości (61 znaków)

∇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
źródło