Problem
Celem jest, jak mówi tytuł, znalezienie n-tej liczby pierwszej, tak że liczba pierwsza-1 jest podzielna przez n.
Wyjaśnienie
Oto przykład, więc rozumiesz pytanie, niekoniecznie jest to sposób, w jaki należy go rozwiązać. Jest to jedynie sposób na wyjaśnienie pytania
biorąc pod uwagę 3 jako dane wejściowe, najpierw przyjrzymy się liczbom pierwszym
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 ...
Następnie wybieramy liczby pierwsze tak, że liczba pierwsza - 1 jest podzielna przez n (3 w tym przypadku)
7 13 19 31 37 43 61 67 73 79 97 103 107 109 127 ...
Następnie wybieramy n-ty termin w tej sekwencji
Wyprowadzilibyśmy 19 dla wejścia 3
Uwaga
Możemy również myśleć o tym jako o n-tej liczbie pierwszej w sekwencji {1, n + 1, 2n + 1, 3n + 1 ... kn + 1}, gdzie k jest dowolną liczbą naturalną
Przypadki testowe
1 --> 2
2 --> 5
3 --> 19
4 --> 29
100 --> 39301
123 --> 102337
code-golf
number
number-theory
primes
Ando Bando
źródło
źródło
Odpowiedzi:
05AB1E ,
98 bajtów05AB1E wykorzystuje kodowanie CP-1252 .
Oszczędność bajtu dzięki Osable
Wypróbuj online!
Wyjaśnienie
źródło
µN¹*>Dp½
który oszczędza jeden bajt i przyspiesza obliczenia.Python 2, 58 bajtów
źródło
Mathematica, 48 bajtów
Funkcja bez nazwy, która przyjmuje pojedynczy argument, który nazywa
n
. Generuje listę pierwszychn^3
liczb pierwszych, wybiera te, które są zgodne z 1 modułemn
, a następnie pobieran
element th wyniku. Działa w ciągu kilku sekund na wejściu 123.Obecnie nie wiadomo, czy wśród pierwszych
n^3
liczb pierwszych zawsze występuje choćby jedna liczba pierwsza , która odpowiada 1 modulon
, a tym bardziejn
ich mniej . Algorytm można jednak udowodnić (przynajmniej dla dużychn
) w oparciu o ogólną hipotezę Riemanna !źródło
Haskell,
5947 bajtówPrzykład użycia:
f 4
->29
.Jak to działa:
Edycja: Dzięki @Damien za 12 bajtów, usuwając test podzielności i patrząc tylko na wielokrotności.
źródło
f n=[p|p<-[1,n+1..],all((<2).gcd p)[2..p-1]]!!n
Galaretka , 9 bajtów
Wypróbuj online!
Jak to działa
źródło
Java 7, 106 bajtów
Nie golfowany:
Kod testowy:
Wypróbuj tutaj (w ostatnim przypadku testowym przekroczono limit czasu dla ideone)
Wydajność:
źródło
System.out.println
one w większości dodawane, więc widzisz, jakich danych użyłem, aby dać pokazany wynik, i wszystko jest również podane na wypadek, gdyby ktoś chciał skopiować i wkleić go w swoim środowisku IDE, aby się pobawić.Nasm 679 bajtów (instrukcja Intel 386 cpu 120 bajtów)
ten jest nieprzylepiony i wyniki
źródło
Właściwie 13 bajtów
Zapraszamy do gry w golfa! Wypróbuj online!
Ungolfing
źródło
Common Lisp, 162 bajty
Stosowanie:
Nie golfowany:
Niektóre z tych
loop
konstrukcji można prawdopodobnie skrócić wdo
pętle, ale na teraz to mam.źródło
MATL , 12 bajtów
Wypróbuj online!
(W przypadku danych wejściowych
123
limit czasu upływa w kompilatorze online, ale działa offline).Wyjaśnienie
źródło
Perl,
7776 + 1 = 77 bajtówUżywa wyrażenia regularnego testowania, aby ustalić, czy
$p
jest liczbą pierwszą, i upewnia się, że jest zgodny z 1 modem danych wejściowych (jedynymi nieujemnymi liczbami całkowitymi poniżej 2 są 0 i 1, ale nie może być 0, jeśli jest liczbą pierwszą, więc musi be 1. zapisuje 1 bajt ponad==1
).źródło
(1 x++$.)!~/^(11+?)\1+$/&&($.%$_<2)&&push@a,$.while@a<$_;say$a[-1]
to (o tym mówiłem w poprzednim komentarzu). Jednak dane wyjściowe (którejkolwiek z wersji) wydają się niepoprawne przez co najmniej 2 i 3 ...Mathematica 44 bajtów
Bardzo szybki. Wykorzystuje pomysł z „Notatki”
Wydajność
źródło
Perl 6 ,
46 3937 bajtówźródło
Java 8, 84 bajtów
Grał w golfa
Bez golfa
Wyjaśnienie
Rozwiązanie inspirowane kilkoma innymi odpowiedziami. Funkcja jest lambda, która oczekuje pojedynczej int.
n>1?i:2
Jest tani siekać, bo nie mogłem wymyślić lepszego sposobu, aby rozważyć przypadek n = 1.To rozwiązanie przekroczyło limit czasu w Ideone, ale zostało przetestowane dla wszystkich przypadków testowych. Upłynął limit czasu, ponieważ aby zgolić kilka bajtów, wyjąłem jawne
j<i
sprawdzenie w wewnętrznej pętli. Jest to głównie sugerowane przezi%j>0
... z wyjątkiem przypadkui=1
ij=2
(pierwszej iteracji), w którym to przypadku pętla działa, dopóki j się nie przepełni (zakładam, że). Następnie działa poprawnie dla wszystkich iteracji później.Wersja, która nie przekracza limitu czasu, jest o kilka bajtów dłuższa, zobacz tutaj!
źródło
Rakieta 109 bajtów
Nie golfowany:
Testowanie:
Wydajność:
źródło
Ruby 64 bajty
Nazywany tak:
Ponadto ta aplikacja wiersza polecenia działa:
tak się nazywa
ale nie jestem pewien, jak policzyć postacie. Myślę, że mogę zignorować nazwę języka, ale
-rprime
przed nazwą skryptu muszę wstawić spację i, więc jest ona nieco krótsza i wynosi 63. . .źródło
R, 72 bajty
Strasznie nieefektywny i powolny, ale działa. Odczytuje dane wejściowe ze standardowego wejścia, a następnie używa
isPrime
funkcji znumbers
pakietu, aby znaleźć liczby pierwsze. Reszta sprawdza tylko, czyprime - 1
można go podzielićn
.źródło
JavaScript (ES6), 65 bajtów
Używa testera pierwotności wyrażenia regularnego, ponieważ jest to: a) 8 bajtów krótszych ib) mniej rekurencyjnych niż moje czyste podejście rekurencyjne.
źródło
Axiom 64 bajty
czy ktoś wie jak pisać powyżej przy użyciu strumieni Axiom? ... jakiś przykład
Wpisz: Tuple NonNegativeInteger
źródło