Apakah itu kura-kura prima?

28

Seperti yang kita semua tahu, itu kura-kura sepanjang jalan . Tapi apakah ini juga prima?

Sejumlah dianggap "penyu-prima" jika memenuhi kondisi berikut:

1) It is prime.
2) It is possible to remove a single digit leaving a prime number.
3) Step 2 can be repeated until left with a single digit prime.

Sebagai contoh, 239adalah "turtle-prime", karena dapat direduksi menjadi 23salah satu 2atau 3keduanya, keduanya prima. Itu juga bisa dikurangi sampai 29saat itu 2. 151bukan penyu, karena mengurangi ke 15(bukan prime), 51(bukan prime), atau 11. 11adalah prima, tetapi hanya dapat mengurangi menjadi 1, yang tidak.

Diberi bilangan bulat positif, tentukan apakah bilangan bulat itu "prima-penyu" Keluaran Anda bisa dalam bentuk apa pun asalkan memberikan hasil yang sama untuk nilai apa pun yang benar atau salah.

Kasus uji:

input -> output
1     -> false
2     -> true
17    -> true
19    -> false
239   -> true
389   -> false

Mencetak gol

Ini , jadi jawaban tersingkat di setiap bahasa menang!

Tuan Farquaad
sumber
5
Terkait
Magic Octopus Guci
@MagicOctopusUrn WOW
Keyu Gan
8
Sebenarnya terkait
FryAmTheEggman
3
Bisakah kita mengambil input sebagai daftar digit?
totallyhuman
1
Kondisi Anda mengatakan bahwa semua bilangan prima satu digit bukan bilangan prima penyu. Kondisi 2 gagal: tidak mungkin untuk menghapus digit dan masih meninggalkan bilangan prima, karena menghapus satu-satunya digit tidak meninggalkan apa pun.
hvd

Jawaban:

6

Jelly , 16 byte

DŒPḊṖLÐṀḌ߀¬Ȧ<ÆP

Cobalah online!

Bagaimana itu bekerja

DŒPḊṖLÐṀḌ߀¬Ȧ<ÆP  Main link. Argument: n

D                 Decimal; convert n to base 10.
 ŒP               Powerset; get all sub-arrays of n's decimal digits.
   Ḋ              Dequeue; remove the first sub-array (empty array).
    Ṗ             Pop; remove the last sub-array (all of n's digits).
     LÐṀ          Maximal by length; keep those of the remaining subarrays that
                  have maximal length. This keep exactly those sub-arrays that have
                  one (and only one) digit removed. If n < 10, this yields an empty
                  array. Without Ḋ, it would yield [[]] instead.
        Ḍ         Undecimal; turn the generated digit arrays into integers.
         ߀       Recursively map the main link over the generated integers.
           ¬      Negate; map 1 to 0 and 0 to 1.
            Ȧ     Any and all; yield 0 if the array is empty (n < 10) or any of the
                  recursive calls returned 1 (mapped to 0). If all calls returned
                  0, this will yield 1.
              ÆP  Test n for primality, yielding 1 for primes, 0 otherwise.
             <    Test if the result to the left is less than the result to the
                  right. This is possible only if the left result is 0 (n < 10 or
                  removing a digit results in a turtle prime) and the right result
                  is 1 (n itself is prime).
Dennis
sumber
Lebih banyak Jelly ajaib!
Sobat
7

Haskell , 104 102 99 98 97 95 91 byte

p x=product[2..x-1]^2`mod`x>0
f[]=1>0
f x|y<-zip[0..]x=or[f[snd b|b<-y,b/=a]|a<-y,p$read x]

Cobalah online!

Penjelasan

Pertama, kami membuat tes primality

p x=product[2..x-1]^2`mod`x>0

Ini menggunakan Teorema Wilson untuk menentukan keutamaan suatu input.

Kami kemudian mendeklarasikan base case, yang akan menyatakan bahwa string kosong itu benar.

f[]=1>0

Sekarang kita mendefinisikan fungsi sebenarnya

f x|y<-zip[0..]x=or[f[snd b|b<-y,b/=a]|a<-y,p$read x]

Kami menggunakan penjaga pola untuk mengikat zip[0..]xke y, karena kita perlu menggunakannya dua kali kemudian. Kami kemudian menegaskan jawabannya adalah

or[f[snd b|b<-y,b/=a]|a<-y,p$read x]

[[snd b|b<-y,b/=a]|a<-y]adalah semua angka yang merupakan digit yang dihapus dari input kami. Jadi kami menegaskan bahwa setidaknya satu dari angka-angka ini adalah benar untuk f. Untuk memastikan bahwa angka komposit salah, kami menambahkan prime$read x. Jika angkanya tidak prima, daftar akan kosong dan anydaftar kosong salah.

Wisaya Gandum
sumber
1
−2 byte: any f[[or[f[
Anders Kaseorg
1
−4 byte: [b|(i,b)<-y,i/=a]|(a,_)<-y[snd b|b<-y,b/=a]|a<-y
Anders Kaseorg
6

R, 124 122 120 113 95 93 106 105 byte

 g=pryr::f(`if`(gmp::isprime(sum(x*10^((l<-sum(x|1)-1):0))),any(!l,sapply(0:l+1,function(z)g(x[-z]))),!1))

Yang mengevaluasi fungsi:

function (x) 
if (gmp::isprime(sum(x * 10^((l <- sum(x | 1) - 1):0)))) any(!l, 
    sapply(0:l + 1, function(z) g(x[-z]))) else !1

Solusi rekursif. Mengambil input sebagai daftar digit.

Memiliki 2 pernyataan logis:

  1. Apakah xprima saat digabung?

  2. Apakah salah satu dari yang berikut TRUE:

    1. Apakah panjangnya xnol? Ini adalah kondisi terminasi terakhir kami.

    2. Apakah f TRUEuntuk subset dari x?

Pernyataan pertama memastikan kami tetap bekerja dengan bilangan prima saja. Yang kedua melakukan rekursi aktual.

Disimpan dua byte berkat @Giuseppe.

Saya harus mengembalikan sebagian golf saya karena bug, di mana saya menguji dengan definisi fungsi sebelumnya secara tidak sengaja.

R, 98 byte, tidak bersaing

Seperti yang saya sebutkan di komentar, saya membuat paket . Karena tantangan sudah ada sebelum itu, ini bukan persaingan, tetapi saya ingin sedikit memamerkannya. Tidak terlalu jauh, tapi kita akan sampai di sana.

g=pryr::f(`if`(gmp::isprime(RG::C(x)),any(!(l<-sum(x|1)-1),sapply(0:l+1,function(z)g(x[-z]))),!1))

C() adalah fungsi pertama dalam paket, dan mengatur digit angka menjadi angka.

JAD
sumber
Beberapa operasi ini (Melihat Anda sum(x*10^(((l<-sum(x|1))-1):0))) sangat buruk. Saya benar-benar mempertimbangkan untuk membuat paket golf R.
JAD
ini akan menjadi solusi saya tetapi saya tidak bisa membungkus kepala saya di sekitar sapply... Juga saya pikir Anda mungkin ingin melakukan f=pryr::f(...)atau Anda perlu menggunakan fdi sapply.
Giuseppe
1
@Giuseppe Nama huruf tunggal untuk semuanya: D Mengapa tidak memanggil paket gatau semacamnya?
JAD
1
@Giuseppe Menciptakan awal untuk sebuah paket: p Lihatlah: github.com/JarkoDubbeldam/RG
JAD
1
@JarkoDubbeldam cantik. Saya yakin tantangan di masa depan akan memperjelas fungsi tambahan apa yang perlu ditambahkan. Manipulasi string itu besar: sesuatu untuk el(strsplit(x,''))akan menghemat satu ton byte.
BLT
5

Jelly , 19 byte

DJḟЀ`ịDḌḟ0߀¬Ȧ¬aÆP

Cobalah online!

Bagaimana itu bekerja

DJḟЀ`ịDḌḟ0߀¬Ȧ¬aÆP                input:239

D                    decimal         [2,3,9]
 J                   range@length    [1,2,3]
  ḟЀ`               filter out each [[2,3],[1,3],[1,2]]
      ịD             index&decimal   [[3,9],[2,9],[2,3]]
        Ḍ            undecimal       [39,29,23]
         ḟ0          filter out 0    [39,29,23]
           ߀        this@each       [1,1,1]
             ¬       logical not     [0,0,0]
              Ȧ      any and all     0
               ¬     logical not     1
                aÆP  and&is_prime    1

Rekursi tanpa kasus dasar kaki.

Biarawati Bocor
sumber
3

Jelly , 27 26 byte

DµœcL’$Ḍµ€FÆPÐf
×⁵WÇÐĿFṪ<8

Tautan monadik yang mengambil dan mengembalikan bilangan bulat ( 1untuk penyu 0sebaliknya).

Cobalah online!

Bagaimana?

DµœcL’$Ḍµ€FÆPÐf  Link 1: primes by digit removal: list of numbers  e.g. [19790]
D                cast to decimal list (vectorises)                      [[1,9,7,9,0]]
 µ      µ€       monadic chain for €ach:
      $            last two links as a monad:
    L                length                                             5
     ’               decrement                                          4
  œc             combinations without replacement                       [[1,9,7,9],[1,9,7,0],[1,9,9,0],[1,7,9,0],[9,7,9,0]]
       Ḍ         cast from decimal list (vectorises)                    [1979,1970,1990,1790,9790]
          F      flatten (from a list of lists form the for €ach to a single list)
             Ðf  filter keep if:
           ÆP      is prime?

×⁵WÇÐĿFṪ<8  Main Link: number, n             e.g. 1979
 ⁵          literal 10
×           multiply                              19790
              (this is so the first number is tested as prime too)
  W         wrap in a list                        [19790]
    ÐĿ      loop, collecting results (including the input×10) while change still occurs:
   Ç          call the last (1) link as a monad   [[19790],[1979],[197,199,179],[19,17,97,19,19,17,19,79],[7,7,7,7],[]]
      F     flatten                               [19790,1979,197,199,179,19,17,97,19,19,17,19,79,7,7,7,7]
       Ṫ    tail                                  7
        <8  less than 8?                          1
              (if a single digit prime was reached this will be 1
               otherwise it will be 0
               e.g. an input of 4 yields 40 at the end which is not <8)
Jonathan Allan
sumber
1
Sangat menarik melihat dua jawaban Jelly yang jauh berbeda. Mari kita lihat siapa yang bisa memotong lebih kecil.
Lord Farquaad
2

Ruby , 72 57 + 8 = 80 65 byte

Menggunakan -rprimebendera. -15 byte dari histokrat!

f=->n{n==''||n.to_i.prime?&!n.scan(/./){f[$`+$']&&break}}

Cobalah online!

Nilai Tinta
sumber
Anda bisa menggantinya &&!!dengan adil &, itu akan melemparkan hasilnya ke boolean. Panggilan rekursif Anda juga bisa sedikit lebih pendek menggunakan perlisma:!n.scan(/./){f[$`+$']&&break}}
histokrat
@ histokrat Ah ya, saya lupa bahwa saya tidak benar-benar memerlukan hubungan pendek boolean untuk bagian terakhir karena kondisi awal. Apakah Anda tahu mengapa n.scantriknya bekerja seperti itu?
Nilai Tinta
1
Ya, dua variabel global yang ada diatur ke string ke kiri dan kanan pertandingan paling baru, jadi menggabungkan mereka memberi Anda string dikurangi karakter satu. Karena kita memerlukan status pada setiap titik dalam iterasi, kita tidak dapat melakukan hal seperti itu .scan.find, tetapi kita dapat secara manual keluar dari lingkaran kesuksesan. Jika kita putus, scankembali nil, jika tidak maka akan mengembalikan string yang selalu benar.
histokrat
2

Java, 220 byte

Cobalah online!

Golf:

boolean t(String n){int l=n.length();if(f(x->{for(int i=2;i<x;)if(x%i++==0)return 1<0;return x>1;},new Integer(n)))if(l<2)return 1>0;else for(int i=0;i<l;)if(t(n.substring(0,i)+n.substring(++i,l)))return 1>0;return 1<0;}

Tidak Terkumpul:

  boolean t(String n) {
    int l = n.length();
    if (f(x -> {
      for (int i = 2; i < x;) {
        if (x % i++ == 0) {
          return 1 < 0;
        }
      }
      return x > 1;
    } , new Integer(n))) {
      if (l < 2) {
        return 1 > 0;
      }
      else {
        for (int i = 0; i < l;) {
          if (t(n.substring(0, i) + n.substring(++i, l))) {
            return 1 > 0;
          }
        }
      }
    }
    return 1 < 0;
  }

sumber
Abaikan komentar saya sebelumnya. Tapi Anda bisa bermain golf untuk ini: boolean t(String n){int l=n.length(),x=new Integer(n),i;for(i=2;i<x;x=x%i++<1?0:x);if(x>1)if(l<2)return 1>0;else for(i=0;i<l;)if(t(n.substring(0,i)+n.substring(++i,l)))return 1>0;return 1<0;}( 191 byte )
Kevin Cruijssen
Anda dapat menyimpan beberapa byte dengan mengembalikan 1 dan 0 alih-alih benar dan salah.
Nevay
@Nevay Itu akan bekerja di C ++, tetapi tidak di Java. Integer tidak dapat secara implisit dikonversi menjadi boolean.
1
Tidak yakin tetapi dari mana datangnya f?
Roman Gräf
Pertanyaannya menyatakan bahwa nilai apa pun dapat digunakan untuk benar / salah; satu-satunya tempat di mana Anda memerlukan hasil boolean dari metode ini adalah dalam kondisi if terakhir (di mana Anda dapat menambahkan >0untuk mengonversi int menjadi boolean) yang harus menyimpan 2 * 2 + 1 * 4 = 8 byte dalam versi Kevin Cruijssen.
Nevay
1

05AB1E , 28 27 byte

Solusi berulang.

¸[D0èg2‹#εæ¨D€gZQÏDpÏ}˜]p1å

Cobalah online!

Penjelasan

¸                              # wrap input in a list
 [                             # start a loop
  D0èg2‹#                      # if the length of the first element is less than 2, break
         ε                     # apply to each element in the list
          æ                    # compute powerset
           ¨                   # remove last element (the full number)
            D€gZQÏ             # keep only the elements whose length is the max length
                  DpÏ          # keep only primes
                     }         # end apply
                      ˜        # flatten list
                       ]       # end loop
                        p1å    # is any element in the resulting list prime
Emigna
sumber
1

Python 2 , 132 124 119 byte

-8 Terima kasih kepada @WheatWizard

-5 Terima kasih kepada @LeakyNun

p=lambda i:i>1and all(i%v for v in range(2,i))
f=lambda n:n<'0'or any(f(n[:i]+n[i+1:])for i in range(len(n)))*p(int(n))

Cobalah online!

Tidak bisa memikirkan apa pun untuk mengasahnya tanpa pemeriksa utama bawaan. Mengambil nomor sebagai string (saya berasumsi ini mengingat OP mengizinkan daftar angka, tetapi jika tidak +14 byte untuk lambda lain), dan secara rekursif menghitung setiap turtleness nomor "turtled".

Arnold Palmer
sumber
2
Tes Shorter Primality
Wheat Wizard
Saya pikir f=lambda n,i=0:n==''or p(int(n))and i<len(n)and(f(n[:i]+n[i+1:])or f(n,i+1))menghemat satu byte. Seseorang dengan keterampilan golf Python yang lebih baik mungkin bisa mempersingkat itu lebih jauh.
Neil
@Neil, itu memang menyimpan byte, tetapi kata-kata "output yang sama untuk nilai kebenaran atau falsey" mencegah saya dari mengambilnya, karena memasukkan 1 mengembalikan 0 bukannya Salah seperti kasus-kasus lain (karena pemeriksaan -8 keaslian) . Jika OP memungkinkan output yang berbeda (meskipun identik), maka saya akan mengubahnya.
Arnold Palmer
1
Maaf, saran saya sebelumnya tidak valid. 119 byte
Leaky Nun
1

C #, 355 byte

namespace System{using B=Numerics.BigInteger;class A{static void Main(){Console.WriteLine(D(Console.ReadLine()));}static bool P(B x){if(x<2)return 1<0;B r=1;for(int i=1;i<=x-1;i++)r*=i;return(r+1)%x==0;}static bool D(string x){if(x.Length==0)return 1>0;bool b;if(b=P(B.Parse(x))){var n=1<0;for(int i=0;i<x.Length;i++)n|=D(x.Remove(i,1));b&=n;}return b;}}}

Cobalah online!

Golf kode pertama saya, jadi saya harap saya melakukannya dengan baik. Saya tidak bisa memikirkan cara untuk membuatnya lebih kecil (selain menggunakan int bukan BigInteger, tapi saya melakukannya sehingga akan bekerja untuk semua test case yang disediakan). Bagaimanapun, ini adalah format yang sama:

namespace System
{
    using B = Numerics.BigInteger;
    class A
    {
        static void Main()
        {
            Console.WriteLine(D(Console.ReadLine()));
        }

        static bool P(B x)
        {
            if (x < 2)
                return 1<0;
            B r = 1;
            for (int i = 1; i <= x - 1; i++)
                r *= i;
            return (r + 1) % x == 0;
        }

        static bool D(string x)
        {
            if (x.Length == 0)
                return 1>0;
            bool b;
            if (b = P(B.Parse(x)))
            {
                var n = 1<0;
                for (int i = 0; i < x.Length; i++)
                    n |= D(x.Remove(i, 1));
                b &= n;
            }
            return b;
        }
    }
}
Grzegorz Puławski
sumber
0

PHP , 164 byte

function t($n){for($i=1;++$i<$n;)if($n%$i<1)return 0;if($n<10)return $n>1;foreach($r=str_split($n)as$k=>$v){$q=$r;array_splice($q,$k,1);$z|=t(join($q));}return $z;}

Cobalah online!

Mulailah dengan menguji angka untuk primality, kemudian loop melalui digit sebagai array, muncul masing-masing dan bergabung dengan sisanya kembali bersama-sama dan memberi makan mereka secara rekursif melalui fungsi lagi. Setiap tautan ke bawah melakukan logika ATAU dengan jalur yang lebih rendah, hanya mengembalikan truejika ada setidaknya satu jalur dari semua bilangan prima.

Xanderhall
sumber
0

Javascript 167 byte

n=>{a=[];for(i=1;i++<=n;)a.every(x=>i%x)?a.push(i):0;b=k=>(s=''+k,a.indexOf(k)>-1&&(k<10||[...s].some((x,i)=>(r=[...s],r.splice(i,1),b(~~(r.join('')))))));return b(n)}

Penjelasan

n=>{
    a=[];                             // create array to store primes in
    for(i=1;i++<=n;)                  // iterate from 2 to n
        a.every(x=>i%x)?a.push(i):0;  // if i % x is truthy for all x in a,
                                      // then i is prime
    b=k=>(                            // function to test is k is turtle prime
        s=''+k,                       // convert k to a string
        a.indexOf(k)>-1 && (          // if k is prime and
            k<10 ||                   // k is a single digit or
            [...s].some((x,i)=>(      // iterate over the digits of k
                                      // and check to see if, by removing each
                                      // any of the resulting numbers is turtle prime
                                      // ... is spread operator
                                      // [...s] converts string s to an array of characters 
                r=[...s],             // convert s to an array again,
                                      // importantly, this cannot be the same array
                                      // we created above, as we need to
                r.splice(i,1),        // splice out the ith element of the array
                b(~~(r.join('')))     // join the array to a string, convert to int,
                                      // and check if this number is turtle prime
                                      // ~ is bitwise negate, implicitly converts to int first before negating
                                      // ~~ negates the negation, getting us the int
            ))
        )
    );
    return b(n)
}

sangat penting
sumber