Perdana n-digit terkecil yang hanya berisi digit ini

26

Anda harus membuat perdana terkecil dengan ndigit, dan hanya akan berisi digit yang ditentukan dalam daftar k.

Contoh:

Memasukkan:

4
1 2

Untuk ini, Anda harus menghasilkan perdana terkecil dengan 4digit, dan perdana itu hanya boleh berisi digit 1dan 2.

Keluaran:

2111

Memasukkan:

10
0 4 7 

Keluaran:

4000000007

Memasukkan:

6
5 5 5 5 5 5 5 5 5 5 1 5 5 5 5 5 5 5 5 5 5

Keluaran:

115151

Anda dapat menjamin bahwa input akan selalu dalam format yang Anda tentukan, dan Anda dapat melakukan apa saja jika Anda mendapatkan input yang tidak valid (seperti input menjadi satu digit n, tanpa k.)

Jika tidak ada solusi untuk input tersebut, program Anda diizinkan untuk melakukan salah satu dari yang berikut:

  • Mencetak banana
  • Lempar kesalahan
  • Jalankan selamanya
  • Ada yang lain

Karena ini adalah , cobalah membidik kode terpendek.

Input dapat dalam format apa pun yang Anda tentukan. Misalnya, jika Anda ingin input Anda seperti salah satu dari yang berikut ini, itu tidak masalah.

4
[1, 2]

[1,2]4

1,2
4

4 12

Anda dapat menulis suatu program atau fungsi, dan itu harus mengembalikan nilai yang benar atau mencetaknya.

Ruang kosong diizinkan di mana saja.

Tantangan ini diinspirasi oleh A036229 .

Okx
sumber
2
Pertanyaan wajib: Bisakah kita menggunakan basis? (Tantangannya jauh lebih mudah di unary.)
flawr
Dapatkah solusinya memiliki angka nol di depan jika nol adalah salah satu digit input?
Luis Mendo
@ flawr tentu saja tidak, saya pikir itu mungkin datang di bawah celah standar (jika tidak, perlu ditambahkan)
Okx
1
@LuisMendo saya tidak akan menghitung itu sebagai nomor 'tepat', jadi tidak.
Okx
Bisakah daftar menjadi himpunan literal? Dan karakter bukan bilangan bulat? (@xnor's Python answer menggunakan itu)
mbomb007

Jawaban:

4

Brachylog (2), 8 byte

j₍oᵐ∋ᵐcṗ

Cobalah online!

Sangat lambat pada masalah yang memiliki banyak kemungkinan digit, atau yang mengandung 0 di set digit yang mungkin (itu berfungsi dalam kasus ini; hanya saja itu jauh lebih lambat sehingga TIO habis waktu kecuali masalahnya sangat sederhana). Seperti biasa untuk Brachylog, ini adalah fungsi, bukan program lengkap.

Input diambil dalam format [ndigits,[list of digits]], mis [10,[[0,4,7]]].

Penjelasan

j₍oᵐ∋ᵐcṗ
j₍        Make a number of copies of the second element equal to the first element
  oᵐ      Sort each (ᵐ) of those copies (evaluation order hint)
    ∋ᵐ    Take one element from each of those copies
      c   Concatenate those elements to form an integer (asserts no leading 0)
       ṗ  producing a prime number

Dilihat dari sudut pandang deklaratif murni, ini mengatakan "menemukan bilangan prima, dengan jumlah digit yang diberikan, di mana semua digit adalah salah satu digit yang diberikan". Untuk menemukan nomor terkecil , kami menggunakan petunjuk urutan evaluasi untuk memastikan urutan kami menguji angka terkecil hingga terbesar; dalam hal ini, membuat keputusan di dekat awal daftar kurang rentan terhadap perubahan daripada keputusan di akhir (ini adalah tatanan alaminya, yang kebetulan sama dengan leksikografis dan urutan numerik pada bilangan bulat), dan dengan demikian {o∋}ᵐmemiliki dua urutan evaluasi mengisyaratkan, "variasikan beberapa digit terakhir terlebih dahulu" (dari tatanan alamiah) sebagai petunjuk yang lebih penting, dan "periksa digit yang lebih kecil sebelum digit yang lebih besar" (dari osebelum, yang bertindak sebagai petunjuk dalam konteks ini) sebagai tiebreak. {o∋}ᵐdapat ditulis sebagai setara oᵐ∋ᵐdengan menyimpan byte.


sumber
12

Paket Bash + bsd-games, 28 byte

  • 18 byte disimpan berkat @Dennis.
primes 1|egrep -wm1 [$2]{$1}

Input diberikan pada baris perintah sebagai n diikuti oleh k sebagai daftar digit yang tidak dibatasi.

Cobalah online.

Trauma Digital
sumber
9

Python 2 , 66 byte

f=lambda n,s,k=1,p=1:10**~-n<p%k*k<s>=set(`k`)or-~f(n,s,k+1,p*k*k)

Cobalah online!

Mengambil input seperti f(3,{'9','3','8'}).

Python tidak memiliki built-in untuk bilangan prima, sehingga fungsi menghasilkan mereka menggunakan Teorema Wilson untuk memeriksa setiap nilai potensial kpada gilirannya untuk menjadi prima.

Ketidaksetaraan dirantai 10**~-n<p%k*k<s>=set(`k`)menggabungkan tiga kondisi pada k:

  • 10**~-n<k: kmengandung setidaknya ndigit. Kita tidak perlu memeriksa dengan tepat karena jika kita mencapai lebih banyak digit, pasti tidak ada solusi
  • p%k>0: kadalah prima, melalui kondisi Teorema Wilson dengan p=(n-1)!^2. Karena p%k0 atau 1, ini dapat digabungkan dengan kondisi sebelumnya seperti10**~-n<p%k*k
  • s>=set(`k`): Semua digit dalam kberada di set s. Ini dapat disambungkan karena Python 2 menganggap set lebih besar dari angka.

Jika saat kini tidak memenuhi semua ini, fungsi berulang k+1, menambahkan 1 ke output yang dihasilkan. Karena output berakhir dengan Trueyang sama dengan 1, dan kdimulai pada 1, outputnya adalah k. Pelacakan paralel ini kmenghasilkan ketukan klangsung pada kesuksesan.

Tidak
sumber
Wow - penggunaan luar biasa dari Teorema Wilson!
Chandler Watson
5

JavaScript (ES7), 100 byte

Mengambil input sebagai jumlah digit ndan string digit yang diizinkan sdalam sintaks currying (n)(s). Kembali undefinedjika tidak ada solusi yang ditemukan.

Bekerja agak cepat hingga 6 digit, mungkin bekerja untuk 7 dan tentunya terlalu lambat - dan memori haus - lebih dari itu.

n=>s=>(a=[...Array(10**n).keys()]).find(i=>eval(`/[${s}]{${n}}/`).test(i)&&a.every(j=>j<2|j==i|i%j))

Uji

Arnauld
sumber
Apa yang akan saya lakukan, kecuali mungkin dengan tes primality yang berbeda. Saya akan melihat bagaimana cara saya dibandingkan dengan milik Anda ...
ETHproduksi
@ ETHproductions Saya mulai dengan tes primality rekursif tetapi itu akan membatasi hingga 4 digit (atau mungkin sedikit lebih pada beberapa browser?)
Arnauld
Pikiran pertama saya untuk solusi rekursif adalah empat byte lebih pendek, tetapi ia melempar kesalahan untuk jumlah besar. Saya punyan=>s=>[...Array(10**n).keys()].find(i=>eval(`/[${s}]{${n}}/`).test(i)&(p=j=>i%--j?p(j):j==1)(i))
ETHproduksi
@ ETHproduksi Saya juga tergoda untuk menggunakan & alih-alih &&. Namun dari segi kinerja, ini byte yang sangat mahal.
Arnauld
Versi Chrome saat ini mendukung TCO jika Anda mengaktifkan bendera "enable-javascript-harmoni" (buka saja chrome: // flags dan temukan opsi itu)
ETHproductions
4

Jelly , 12 byte

DL×ÆP
ṗḌÇÐṀṂ

Mengambil satu set dan integer sebagai argumen baris perintah. Mencetak 0 jika tidak ada solusi.

Cobalah online!

Bagaimana itu bekerja

ṗḌÇÐṀṂ  Main link. Left argument: A (digit set/array). Right argument: n (integer)

ṗ       Cartesian power; yield all arrays of length n that consist only of elements
        of the array A.
 Ḍ      Undecimal; convert all generated digit arrays to integers.
  ÇÐṀ   Keep only elements for which the helper link returns a maximal result.
     Ṃ  Take the minimum.


DL×ÆP   Helper link. Argument: k (integer)

D       Decimal; convert k into the array of its base 10 digits.
 L      Take the length.
   ÆP   Test if k is a prime number. Yields 1 or 0.
  ×     Multiply the length and the Boolean.
Dennis
sumber
3

Pyke, 18 16 byte

j;~p#`ljqi`Q-!)h

Coba di sini!

Berjalan selamanya jika tidak ada nilai yang ditemukan

Biru
sumber
@Okx sekarang harus cukup cepat untuk menjalankan sebagian besar jika tidak semua test case sekarang
Blue
@Okx Anda tahu bahwa Anda dapat mengunduh Pyke dan menjalankannya secara offline jika Anda ingin mengujinya sepenuhnya tanpa batas waktu?
Biru
Oh maaf. Saya pikir itu kodenya. Ternyata batas waktu sekitar empat detik yang tidak terlalu banyak.
Okx
3

Mathematica, 64 byte

FirstCase[Tuples@##,x:{f_,___}/;f>0&&PrimeQ[y=FromDigits@x]:>y]&

Fungsi murni di mana argumen pertama adalah daftar (diurutkan) dari digit yang diizinkan dan argumen kedua adalah panjang yang diizinkan. Tuples@##menghitung semua daftar angka diperbolehkan dari panjang diizinkan, maka kita menemukan FirstCaseyang cocok x:{f_,___}sehingga digit pertama fadalah tidak 0dan integer y=FromDigits@xadalah perdana dan menggantikannya dengan y.

ngenisis
sumber
2
Itu keren bagaimana Anda menggunakan /;tes untuk memilih tuple tetapi juga :>mengkonversi ke format output yang diinginkan. (Saya melihat dalam dokumentasi yang dibolehkan, tetapi hanya setelah membaca jawaban ini!) Anda harus menentukan bahwa fungsi Anda membutuhkan angka yang diizinkan untuk diurutkan: itu memberikan jawaban yang salah 3331alih-alih 3313jika dipanggil dengan [{3,1},4].
Greg Martin
@ngenisis bagaimana Select[FromDigits/@Tuples[Sort@#,#2],PrimeQ][[1]]&@@#&?
martin
@martin Itu tidak memperhitungkan tupel yang dimulai dengan 0dan @@#&tampaknya berlebihan.
ngenisis
@ngenisis maaf - tidak memperhitungkan itu
martin
3

Brachylog , 15 byte

tL∧?h~lṗ.dẹp⊆L∧

Cobalah online!

Ini cukup lambat.

Penjelasan

tL                Input = [H, L]
  ∧
   ?h~l .         The Output is a variable of length H
       ṗ.         The Output is a prime number
          ẹ       The Output's digits...
        .d        ...when removing duplicate digits...
           p      ...is a permutation...
            ⊆L    ...of an ordered subset of L
              ∧
Fatalisasi
sumber
2

JavaScript (ES6), 86 byte

Mengambil input melalui sintaks currying, misalnya, (4)('12')

n=>(d,F=(i,P=j=>i%--j?P(j):1==j)=>P(i)&&`${i}`.match(`^[${d}]{${n}}$`)?i:F(i+1))=>F(2)

'use strict';

const G=n=>(d,F=(i,P=j=>i%--j?P(j):1==j)=>P(i)&&`${i}`.match(`^[${d}]{${n}}$`)?i:F(i+1))=>F(2)

const submit = () => {
  console.clear();
  console.log(G(+n.value)(d.value));
}

button.onclick = submit;
submit();
<input id="n" type="number" min="1" value="4" />
<input id="d" type="text" value="12" />
<button id="button">Submit</button>

Untuk dijalankan dalam mode ketat (untuk optimisasi panggilan ekor [TCO] ). Jika lingkungan Anda tidak mendukung TCO, itu akan menghasilkan kesalahan stack overflow untuk bilangan prima yang lebih besar dari tumpukan lingkungan.

Untuk input yang tidak valid itu akan berjalan selamanya.

catatan:

  • Chrome (> = 51) pengguna dapat pergi ke chrome://flags/#enable-javascript-harmonydan mengaktifkan bendera ini untuk menjalankan cuplikan di atas dengan dukungan TCO.
  • Safari (> = 10) mendukung TCO
George Reith
sumber
Saya pikir Anda dapat menyimpan dua byte denganF=i=>(P=j=>i%--j?P(j):1==j)(i)&&...
ETHproduk
@ ETHproductions Tidak bisa karena itu harus dijalankan dalam mode ketat (untuk menghindari stack overflow) dan itu menciptakan variabel global P.
George Reith
Oh, saya tidak menyadari TCO hanya diterapkan dalam mode ketat.
ETHproduk
@ ETHproductions Aye saya juga tidak sampai saya membaca spesifikasi saya memposting XD variasi jawaban pertama saya memang menggunakan pintasan itu sampai saya menyadari itu tidak valid.
George Reith
2

MATL, 17 byte

wlwX"1GXNUStZp)l)

Fungsi ini menerima dua input, bilangan bulat yang menentukan jumlah digit dan larik karakter yang menunjukkan nilai yang mungkin. Dalam hal tidak ada bilangan prima, kesalahan ditampilkan.

Cobalah secara Online!

Penjelasan

        % Implicitly grab two inputs. First as an integer (N), second as a string (OPTS)
w       % Reverse the order of the inputs
l       % Push the literal 1 to the stack
w       % Pull N back to the top of the stack
X"      % Repeat OPTS N times 
1G      % Explicitly grab N again
XN      % Get all N-character combinations of the repeated version of OPTS
U       % Convert each row from a string to a number
S       % Sort them in ascending order
tZp)    % Grab only those that are primes
l)      % Retrieve the first prime
        % Implicitly print the result
Suever
sumber
2

Sage, 62 byte

lambda l,d:[p for p in primes(10^(l-1),10^l)if set(`p`)<=d][0]

Mengambil input dari formulir: f( 4 , {'1','2'} )

busukxuan
sumber
1

Perl 6 , 43 byte

->\n,@k {first *.is-prime&/^@k**{n}$/,^∞}

Berjalan selamanya jika tidak ada solusi.

seseorang
sumber
apa format input?
Okx
1
@Okx: Ini lambda yang mengambil dua argumen: Nomor n, dan daftar k.
smls
1

05AB1E , 17 byte

[¾Øмg¹QiS²Kg0Qiq

Cobalah online!

[¾Ø ¼             # Infinite loop over all primes
   Ð              # Push two extra copies on the stack
     g¹Qi         # If the length of this prime == the first input...
         S²K      # Push this prime without any of the digits in the second input
            g0Qi  # If the length of what remains is 0...
                q # quit
                  # implicitly print this prime
Riley
sumber
1

05AB1E , 22 19 18 byte (-1 @Riley)

[NØ©S¹Kg0Q®g²Q&i®q

Cobalah online!

[                   # infinite loop.
 NØ©                # push nth prime.
    S¹Kg0Q          # see if, without banned digits, it's 0 length.
          ®g²Q&     # see if, it is originally also the length specified.
               i®q  # if true, print result and exit.
Guci Gurita Ajaib
sumber
1
Saya tidak berpikir Anda perlu ,pada akhirnya.
Riley
@Riley panggilan yang bagus!
Magic Octopus Urn
0

Perl5, 77 byte

($n,$d)=@ARGV;/^[$d]{$n}$/&&("x"x$_)!~/^(..+?)\1+$/&&print&&die for 2..10**$n

Jalankan seperti ini:

perl -le '($n,$d)=@ARGV;/^[$d]{$n}$/&&("x"x$_)!~/^(..+?)\1+$/&&print&&die for 2..10**$n' 4 12
Kjetil S.
sumber
0

Ruby, 77 76 byte

->n,l{(10**~-n..10**n).find{|n|(2...n).none?{|x|n%x<1}&&!n.to_s[/[^#{l}]/]}}

Format input: angka dan string.

Contoh:

->n,l{...see above...} [6,"555555555515555555555"]
=> 115151
GB
sumber
0

Perl 6 , 68 byte

->\n,\k{first {.is-prime&&/.**{n}/},+«[X~] 0,|(k.unique.sort xx n)}

Cobalah

Kembali Nil jika tidak ada perdana yang dapat ditemukan.

Diperluas:

->
  \n, # number of digits
  \k  # list of digits
{

  first

    {
        .is-prime
      &&
        / . ** {n} / # exactly 「n」 digits ( in case 「k」 has a 0 )
    },

    \          # turn the following into a list of numbers

    [X[~]]       # cross the following with &infix:<~>

    0,           # append a 0 in case 「n」 was 1
    |(           # slip this list in (flatten)

        k        # the input list of possible digits
        .unique  # only one of each to reduce the search space (optional)
        .sort    # sort it so that the cross meta op returns them sorted

      xx         # list repeat

        n        # 「n」 times
    )
}
Brad Gilbert b2gills
sumber
0

Python 2 + primefac , 91 85 byte

import primefac as P
n,k=input()
p=10**~-n
while set(`p`)!=k:p=P.nextprime(p)
print p

Cobalah online

Inputnya seperti 4,{'1','2'}.

mbomb007
sumber
1,{'1'}bukan input yang valid (karena 1 tidak prima), sehingga Anda dapat melakukan apa pun yang Anda suka di sana.
Oh benar Terima kasih.
mbomb007
0

PHP, 82 byte

for($n=10**--$argv[1];$i-1||a&trim($n,$argv[2]);)for($i=++$n;--$i&&$n%$i;);echo$n;

Mengambil angka dan serangkaian digit dari argumen baris perintah. Jalankan dengan -nr.

kerusakan

for($n=10**--$argv[1];  // $n = smallest number with (argument1) digits
    $i-1||                  // loop while $n is not prime or
    a&trim($n,$argv[2]);    // $n without all digits from (argument2) is not empty
)
    for($i=++$n;--$i&&$n%$i;);  // $i=largest divisor of $n smaller than $n (1 for primes)
echo$n;                 // print
Titus
sumber
0

Java 7, 139 141 byte

long c(int a,String b){for(long n=2,i,x;;n++){for(x=n,i=2;i<x;x=x%i++<1?0:x);if(x>1&(n+"").length()==a&(n+"").matches("["+b+"]+"))return n;}}

+2 byte dengan angka-angka yang mendukung di atas 32-bit (diubah intmenjadi long)

Format input: Integer (yaitu 4) dan String (yaitu "12")

Penjelasan:

long c(int a, String b){                  // Method with the two input parameters specified above
  for(long n = 2, i, x; ; n++){           // Loop from 2 going upwards
    for(x = n, i = 2; i < x; x = x % i++ < 1 ? 0 : x);  // Prime check for `n` 
    if (x > 1                             // if `n` is a prime (if `x` > 1 after the loop above it means `n` is a prime)
         & (n+"").length() == a           // AND if `n` has a length equal to the input integer
         & (n+"").matches("["+b+"]+")){   // AND if `n` only contains the specified digits of the input String (using a regex)
      return n;                           // Then we have our answer
    }
  }                                       // If no answer is available for the given input, it continues looping
}

Kode uji:

Coba di sini.
CATATAN: Test case kedua dinonaktifkan karena loop untuk waktu yang sangat lama ..

class M{
  static long c(int a,String b){for(long n=2,i,x;;n++){for(x=n,i=2;i<x;x=x%i++<1?0:x);if(x>1&(n+"").length()==a&(n+"").matches("["+b+"]+"))return n;}}

  public static void main(String[] a){
    System.out.println(c(4, "12"));
    //System.out.println(c(10, "047"));
    System.out.println(c(6, "555555555515555555555"));
  }
}

Keluaran:

2111
115151
Kevin Cruijssen
sumber