Liczba pierwsza, którą można przycinać w prawo, jest liczbą pierwszą, w której każdy prefiks jest liczbą pierwszą (w bazie 10). Liczba pierwsza skracalna w lewo jest dokładnie odwrotna, gdzie każda postfiks jest liczbą pierwszą (liczby pierwsze zaczynające się od 0 nie są dozwolone). Obie te sekwencje są skończone (istnieje tylko 83 prawe przycinane, podczas gdy są 4260 lewe ścięte).

Musisz napisać program, który przyjmuje jedną liczbę jako dane wejściowe i generuje n- tą liczbę pierwszą możliwą do przycięcia w prawo. Jednak, gdy program jest czytany ułożony do tyłu , powinien wygenerować n- tą lewą możliwą do przycięcia liczbę pierwszą.

Aby uporządkować program do tyłu, podzieliliśmy program na słowa, a następnie odwróciliśmy ich kolejność. Słowo może składać się z dowolnej liczby znaków.

Na przykład jeśli twój program był następujący:

hello world
1234567890

Dopuszczalne byłyby wszystkie możliwe uzgodnienia wstecz:

Podział na każdą postać:

0987654321
dlrow olleh

Podział na białe znaki:

1234567890
world hello

Dowolny podział (rury dodane dla przejrzystości):

hel|lo w|orld
1|23456|7|8|90

908723456orld
1lo whel

Podczas aranżacji programu do tyłu wszystkie białe znaki muszą być wzięte pod uwagę i odwrócone, tak jak każdy inny znak.

Przekazywanie danych wejściowych testu:

1:  2
2:  3
21: 379
60: 239933
83: 73939133

Dane wejściowe testu wstecznego:

1:    2
2:    3
39:   647
187:  29173
4260: 357686312646216567629137

Programy powinny być w stanie działać w rozsądnym czasie (mniej niż minutę)

To jest golf golfowy , więc wygrywa program z najmniejszą liczbą bajtów!

Galaretka , 26 23 bajtów

Naprzód

Ѷp9¶7ÆR2ĿV€$ÆPÐf$ÐĿFị@

Wypróbuj online!

Słowa

Ñ ¶ p 9 ¶ 7ÆR2ĿV€$ÆPÐf$ÐĿFị@

Do tyłu

7ÆR2ĿV€$ÆPÐf$ÐĿFị@¶9p¶Ñ

Wypróbuj online!

Słowa

7ÆR2ĿV€$ÆPÐf$ÐĿFị@ ¶ 9 p ¶ Ñ

Jak to działa

Wszystkie programy Jelly składają się z linków (funkcje Jelly przyjmują), które są oddzielone liniami lub pilcrows ( ¶). Ostatni z nich to główny link ; jest wywoływany automatycznie po uruchomieniu programu.

Program przekazywania działa w następujący sposób.

Ñ                   Helper link. Unused.


p9                  Helper link. Take the Cartesian product with [1, ..., 9].


7ÆR2ĿV€$ÆPÐf$ÐĿFị@  Main link. Argument: n

7ÆR                 Yield all primes up to 7.
             ÐĿ     
            $ÐĿ     Combine the two quicklinks to the left into a monadic chain,
                    and call it repeatedly until the results are no longer unique.
                    Return the array of all intermediate results.
       $              Combine the two links to the left into a monadic chain.
   2Ŀ               Call the helper link on line 2.
     Ṿ€                 Eval each array in the product. This casts to string
                        before evaluating, thus concatenating both numbers.
        ÆPÐf        Filter by primality; keep only primes.
               F    Flatten the resulting array.
                ị@  Retrieve the element at index n.

Program wstecz działa prawie dokładnie tak samo; są tylko dwie różnice.

• Główny link jest teraz Ñ, który po prostu wywołuje link poniżej (zawijanie), tj. Główny link programu przekazującego.

• 9pzamiast p9zwracać odwrócony produkt kartezjański.

Python 2, 143 139 bajtów

I=1
a={2}
def f(s):
 for d in'123456789':u=d[I:]+s+d*I;z=int(u);z+=z<3;z%91>0<2==pow(2,z,z)>a.add(z)<f(u)
f('')
lambda n:sorted(a)[~-n]
I=0

Składa się z pięciu części:

1. I=1
2. Nowa linia
3. a={2}…[~-n]
4. Nowa linia
5. I=0

Więc odwrócenie to po prostu zmiana wartości I.

Wyjaśnienie

Ta funkcja fwykonuje rekurencyjne wyszukiwanie liczb pierwszych skracalnych w lewo (LTP) lub liczb pierwszych skracalnych w prawo (RTP), w zależności od wartości globalnej I. Te wartości zostaną dodane do zestawu a. Następnie lambda n:sorted(a)[~-n]zwraca n-ty.

Zdefiniujmy liść jako LTP, RTP, pewną niezerową cyfrę + LTP lub RTP + jakąś niezerową cyfrę. Są to wszystkie wartości, które fmogą chcieć sprawdzić pierwotność.

Zaprojektowałem pseudopierwszy test Fermata, który działa na wszystkie liście:

(63973 to liczba Carmichaela ).

Jeśli ten test zwróci wartość true, znależy go dodać do zestawu ai powinniśmy kontynuować str(z). Odpowiedzialny fragment kodu to:

z+=z<3;z%91>0<2==pow(2,z,z)>a.add(z)<f(u)

Po pierwsze, chcemy zająć się tą sprawą z == 2. Robimy to po prostu unikając go tutaj i kodując na początku, 2gdy początkowo definiujemy a! (EDYCJA: I nic złego się nie stanie, jeśli również złapiemy z == 1.) Możemy więc założyć, że z ≥ 3teraz.

Przetłumaczyłem niektóre „i” na krótkie łańcuchowe porównanie: pierwsze trzy porównania muszą się udać a.add(z)i f(u)są zawsze oceniane. Oto wszystkie ich role:

1. z%91>0koduje nasz pierwszy warunek. (63973 można podzielić przez 91, co nie jest samym liściem, więc tak go rozpoznajemy).
2. 0<2jest zawsze prawdziwe, ale tworzenie łańcuchów jest krótsze niż and.
3. 2==pow(2,z,z) koduje nasz drugi warunek.
4. pow(2,z,z)>a.add(z)wyzwala dodawanie i jest zawsze prawdziwe, ponieważ set.addzwraca None, a liczby całkowite są zawsze większe niż None.
5. a.add(z)<f(u)wyzwala rekurencję. Jego wartość prawdy jest nieistotna.

Podziękowanie

• Dennis zapisał cztery bajty ( u=[d+s,s+d][I]→ u=d[I:]+s+d*I; z==2→ z<3i sztuczka mod 91 ). Dzięki!