Cetak nth prime yang berisi n

39

Pertanyaan ini akan menjadi twist dalam menemukan nbilangan prima ke-5.

Tantangan

Anda harus menulis sebuah program yang akan mengambil satu input n, dan menampilkan nbilangan prima ke-10 yang representasi desimalnya mengandung representasi desimal nsebagai subtring.

Bingung? Berikut ini beberapa contohnya.

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

Ini adalah , sehingga jumlah byte terendah menang.

Jika ada yang membingungkan, silakan tinggalkan komentar.

ericw31415
sumber
2
Apakah ada OEIS untuk ini? Rasanya seperti harus ada
MayorMonty
@ SpeedyNinja Tidak, saya sudah memeriksa.
Adnan
Terkait
Alex A.
1
Saya tidak percaya bahwa ini membuatnya menjadi nomor 5 dalam Hot Network Questionsdaftar.
ericw31415
Urutan serupa
Nathan Merrill

Jawaban:

12

05AB1E , 8 byte

Kode:

µN¹åNp*½

Penjelasan:

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

Menggunakan pengodean CP-1252 . Cobalah online! .

Adnan
sumber
10

Pyth - 11 byte

e.f&P_Z}`Q`

Test Suite .

Maltysen
sumber
8

Python 2, 67 65 62 byte

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)

Uji di Ideone .

Bagaimana itu bekerja

Kami menggunakan akibat wajar dari teorema Wilson :

akibat dari teorema Wilson

Setiap saat, variabel p sama dengan kuadrat faktorial m - 1 .

Jika k <n , k/nakan menghasilkan 0 dan f disebut secara rekursif. m bertambah, p diperbarui, dan k bertambah jika dan hanya jika m adalah bilangan prima yang mengandung n .

Yang terakhir dicapai dengan menambahkan hasil p%m*(`n`in`m`)ke k . Dengan akibat wajar teorema Wilson jika m adalah prima, p%mmengembalikan 1 , dan jika tidak, ia mengembalikan 0 .

Setelah k mencapai n , kami menemukan q , perdana ke- n yang berisi n .

Kami sedang dalam panggilan berikutnya selama pemeriksaan, jadi m = q + 1 . k/nakan mengembalikan 1 , dan operator bitwise -~akan menambah nomor itu satu kali untuk setiap panggilan fungsi. Karena dibutuhkan panggilan q - 1 ke f untuk meningkatkan m dari 2 ke q + 1 , panggilan terluar ke f akan mengembalikan 1 + q - 1 = q , sebagaimana dimaksud.

Dennis
sumber
6

Bash, 27 byte

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

primes berasal dari bsdgames.

Mengambil input sebagai argumen baris perintah, dan output pada STDOUT.

Gagang pintu
sumber
4

Mathematica, 75 byte

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

Mungkin masih bisa bermain golf.

LegionMammal978
sumber
Ini mungkin solusi tercepat karena menggunakan NextPrime :)
4

Jawa, 194 180 173 171 112 Bytes

Kode:

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

Tidak Disatukan:

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);
    }
}
Semoga Membantu
sumber
Hai, selamat datang di PPCG! Dua hal yang perlu diperhatikan, 1. Anda dapat menghapus dua spasi di P {dan String[] s. Dan 2. Anda saat ini hanya memberikan output 10, tetapi tantangan kode-golf adalah mengambil input ndan memberikan output yang tepat berdasarkan input itu. Juga, Anda mungkin menemukan ini menarik: Tips untuk bermain golf di Jawa.
Kevin Cruijssen
3

Ruby, 62 61 byte

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

Membutuhkan -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
}
Gagang pintu
sumber
3

Julia, 61 60 byte

f(n,k=0,m=1)=k<n&&f(n,k+isprime(m)contains("$m","$n"),m+1)+1

Cobalah online!

Dennis
sumber
3

MATL , 18 byte

`@YqVGVXf?3M]NG<]&

Cobalah online!

Penjelasan

Ini menghasilkan bilangan prima agar menggunakan do...whileloop. Untuk setiap prime, kondisi diuji (dan prime dikonsumsi). Jika puas, prime itu didorong ke stack lagi. Jumlah elemen dalam tumpukan digunakan sebagai jumlah berapa primes kualifikasi yang telah kami temukan. Ketika jumlah mereka cukup, yang terakhir akan ditampilkan.

`         % 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
sumber
1

Bash + GNU coreutils, 66 Bytes

Berbeda dengan solusi @ Doorknob, ini hanya membutuhkan hal-hal yang diinstal pada setiap GNU / Linux:

for((n=2;;n++)){
[ `factor $n|wc -w` -eq 2 ]&&grep $1<<<$n&&exit
}
rexkogitans
sumber
seq 1e20|factor|grep -Po "(?<=: )\d*$2\d$"|sed $1q\;d
Digital Trauma
@DigitalTrauma, otak saya tidak bekerja seperti ini ;-)
rexkogitans
Apakah perlu baris baru?
ericw31415
Setelah itu for((...)){, harus ada spasi atau baris baru, jadi tidak masalah. Sebelum penutupan }, harus ada a ; atau baris baru, jadi tidak masalah juga.
rexkogitans
1

Perl 6 , 41 byte

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

Penjelasan:

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

Uji:

#! /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
sumber
1

Java 8, 192 183 181 171 byte (program penuh)

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

Cobalah online.

Penjelasan:

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 byte (fungsi 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;}

Cobalah online.

Sama seperti di atas, tetapi dengan ninput integer dan tanpa hal-hal kelas verbose.

Kevin Cruijssen
sumber
1
Anda dapat mengganti &&dengan &dan menghapus ?dari regexp Anda.
cliffroot
@cliffroot Terima kasih, telah mengedit pos. Saya selalu lupa tentang &&dan &untuk beberapa alasan ..
Kevin Cruijssen
0

Clojure, 118 byte

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

Hanya mendapatkan elemen ke-n dari urutan angka malas malas yang prima dan ada ndalam representasi string mereka.

Anda dapat mencobanya di sini: https://ideone.com/ioBJjt

cliffroot
sumber
0

Sebenarnya, 16 byte

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

Cobalah online!

Penjelasan:

;$╗`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
sumber
0

PowerShell v2 +, 108 99 byte

Ooof. Kurangnya segala macam perhitungan / pemeriksaan prima bawaan benar-benar menyakitkan di sini.

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

Mengambil input $n, memasuki for()loop tak terbatas . Setiap iterasi, kami menggunakan forloop yang melingkari checker prime PowerShell regex (h / t ke Martin) untuk mengubahnya menjadi generator utama dengan menambah $isetiap kali melalui loop. (Misalnya, menjalankan hanya for(){for(;'1'*++$i-match'^(?!(..+)\1+$)..'){$i}}akan menampilkan2, 3, 5, 7... dipisahkan oleh baris baru).

Kemudian -likecek sederhana untuk melihat apakah $nada di suatu tempat $i, dan menambah counter kami $o. Jika kita telah mencapai di mana $ndan $osama, output $idan exit. Kalau tidak, kita terus melanjutkan foruntuk menemukan prime berikutnya dan proses berulang.

AdmBorkBork
sumber
0

APL (NARS), 39 karakter, 78 byte

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

1π adalah bilangan prima berikutnya ...; uji:

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

tetapi itu sudah pada 20 keluar ruang stack ... Sebaliknya ini di bawah ini tampak ok bahkan jika memiliki panjang lebih lama (61 karakter)

∇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
sumber
0

Tambahkan ++ , 36 byte

L,5*2^RßÞPABDBJVB]dG€Ωezߣ*BZB]A1_$:

Cobalah online!

Cukup tidak efisien. Ulangi setiap bilangan bulatsaya seperti yang saya25x2 dan menyaring komposit dan bilangan prima yang tidak mengandung n. Akhirnya, kami mengambilnnilai th dari integer yang tersisa.

caird coinheringaahing
sumber