Jak wszyscy wiemy, żółwie schodzą w dół . Ale czy jest to również liczba pierwsza?

Liczbę uważa się za „pierwszą żółwia”, jeżeli spełnia następujące warunki:

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.

Na przykład 239jest „żółwiem”, ponieważ można je zredukować do 23jednego 2lub 3obu, które są pierwsze. To również może być zredukowana do 29wtedy 2. 151nie jest liczbą pierwszą żółwia, ponieważ redukuje się do 15(nie pierwsza), 51(nie pierwsza) lub 11. 11jest liczbą pierwszą, ale można ją jedynie zredukować 1, co nie jest.

Biorąc pod uwagę dodatnią liczbę całkowitą, określ, czy jest to „liczba żółwia”. Twój wynik może być w dowolnej formie, pod warunkiem, że daje to samo wyjście dla dowolnej wartości prawdziwej lub falsey.

Przypadki testowe:

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

Punktacja

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w każdym języku!

Galaretka , 16 bajtów

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

Wypróbuj online!

Jak to działa

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

Haskell , 104 102 99 98 97 95 91 bajtów

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]

Wypróbuj online!

Wyjaśnienie

Najpierw przeprowadzamy test pierwszeństwa

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

Wykorzystuje to Twierdzenie Wilsona do ustalenia pierwotności danych wejściowych.

Następnie deklarujemy przypadek podstawowy, który zapewni, że pusty ciąg znaków jest prawdziwy.

f[]=1>0

Teraz definiujemy rzeczywistą funkcję

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

Używamy straży wzór do wiązania zip[0..]xdo y, dlatego musimy używać go dwa razy później. Następnie twierdzimy, że odpowiedź brzmi

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

[[snd b|b<-y,b/=a]|a<-y]to wszystkie liczby, które są cyframi usuwanymi z naszych danych wejściowych. Twierdzimy więc, że co najmniej jedna z tych liczb jest prawdziwa f. Aby upewnić się, że liczby złożone są fałszywe, dodajemy prime$read x. Jeśli liczba nie jest liczbą pierwszą, lista stanie się pusta, a anypusta lista będzie fałszywa.

R, 124 122 120 113 95 93 106 105 bajtów

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

Który ocenia się na funkcję:

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

Rozwiązanie rekurencyjne. Pobiera dane wejściowe jako listę cyfr.

Ma 2 logiczne instrukcje:

1. Czy xłączna jest liczba pierwsza?

2. Czy którykolwiek z poniższych TRUE:

   1. Czy długość jest xniezerowa? To jest nasz końcowy warunek zakończenia.

   2. Czy f TRUEdla dowolnego podzbioru x?

Pierwsze stwierdzenie gwarantuje, że nadal pracujemy tylko na liczbach pierwszych. Drugi dokonuje rzeczywistej rekurencji.

Zaoszczędzono dwa bajty dzięki @Giuseppe.

Musiałem cofnąć niektóre z moich golfów z powodu błędu, w którym przez przypadek testowałem z poprzednią definicją funkcji.

R, 98 bajtów, niekonkurujący

Jak wspomniałem w komentarzach, zrobiłem paczkę . Ponieważ wyzwanie to poprzedza, nie jest to konkurencja, ale chciałem to trochę pokazać. Jak dotąd niewiele, ale się tam dostaniemy.

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() to pierwsza funkcja w pakiecie, która zajmuje się łączeniem cyfr w cyfrę.

Galaretka , 19 bajtów

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

Wypróbuj online!

Jak to działa

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

Rekurencja bez skrzynki podstawowej ftw.

Galaretka , 27 26 bajtów

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

Monadyczny link przyjmujący i zwracający liczby całkowite ( 1dla żółwia 0inaczej).

Wypróbuj online!

W jaki sposób?

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)

Rubinowy , 72 57 + 8 = 80 65 bajtów

Używa -rprimeflagi. -15 bajtów od histocrata!

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

Wypróbuj online!

Java, 220 bajtów

Wypróbuj online!

Gra w golfa:

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

Nie golfowany:

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

05AB1E , 28 27 bajtów

Iteracyjne rozwiązanie.

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

Wypróbuj online!

Wyjaśnienie

¸                              # 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

Python 2 , 132 124 119 bajtów

-8 Dzięki @WheatWizard

-5 Dzięki @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))

Wypróbuj online!

Nie mogę wymyślić niczego, co by go wyostrzyło bez wbudowanego sprawdzania liczb pierwszych. Pobiera liczbę jako ciąg znaków (założyłem, że biorąc pod uwagę PO dozwoloną listę cyfr, ale jeśli nie, to +14 bajtów dla innej lambdy) i rekurencyjnie oblicza turtlenity każdego „żółwia”.

C #, 355 bajtów

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

Wypróbuj online!

Mój pierwszy golf golfowy, więc mam nadzieję, że zrobiłem to dobrze. Nie mogłem wymyślić sposobu, aby uczynić go jeszcze mniejszym (innym niż użycie int zamiast BigInteger, ale zrobiłem to, aby działało dla wszystkich dostarczonych przypadków testowych). Tak czy inaczej, oto ten sam poprawnie sformatowany:

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

Perl 6 , 65 bajtów

my&f={.is-prime&&(10>$_||?grep {f +[~] .list},m:ex/^(.*).(.*)$/)}

Wypróbuj online!

PHP , 164 bajty

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

Wypróbuj online!

Zaczyna się od przetestowania liczby pod kątem pierwszeństwa, a następnie zapętla cyfry jako tablicę, wyskakując z nich i łącząc resztę z powrotem i karmiąc je rekurencyjnie przez funkcję. Każde łącze w dół wykonuje logiczną operację OR z dolnymi ścieżkami, zwracając je tylko truewtedy, gdy istnieje co najmniej jedna ścieżka wszystkich liczb pierwszych.

JavaScript 167 bajtów

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

Wyjaśnienie

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

F=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)}

$('#input').on('keyup', () => $('#output').text(F(parseInt($('#input').val(), 10))))

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<input type="text" id="input" />
<span id="output"></span>