Liczby pierwsze są wszędzie ...
chowają się w Pi
3,141592653 58979 3238 462643 3832 795028841 971693993751
Zdobądźmy te liczby pierwsze!
Wyzwanie
Biorąc pod uwagę liczbę całkowitą n>0
, dowiedz się, ile liczb pierwszych jest ukrytych w pierwszych n
cyfrachPi
Przykłady
Bo n=3
powinniśmy szukać liczb pierwszych w [3,1,4]
. Istnieją 2 Najwyżsi (3,31)
, więc kod powinien Wyjście 2
Na n=10
pierwsze 10 cyfr [3,1,4,1,5,9,2,6,5,3]
i kod powinien wyjście 12
ponieważ [2, 3, 5, 31, 41, 53, 59, 653, 4159, 14159, 314159, 1592653]
były ukryte (i znalazłem!)
Przypadki testowe
wejście -> wyjście
1->1
3->2
13->14
22->28
42->60
50->93
150->197
250->363
500->895
Zasady
Kod musi być w stanie znaleźć wszystkie liczby pierwsze przynajmniej nan=50
tak, można zakodować pierwsze 50 cyfr o Pi
jeśli lubisz
Wpisy hardcoding odpowiedzi są nieważne
To jest golf golfowy. Najkrótsza odpowiedź w bajtach wygrywa!
Odpowiedzi:
05AB1E ,
108 bajtów-2 bajty dzięki Adnanowi (
p
wektoryzacja)Wypróbuj online! (zadziała do n = 98413, ale będzie bardzo powolny nawet dla n = 50 ze względu na konieczność przetestowania tak dużych liczb pod kątem pierwszeństwa - TIO kończy się po 60 sekundach dla n = 50).
W jaki sposób?
źródło
<žsþŒÙpO
powinien działać przez 8 bajtówp
wektoryzuje dzięki!Mathematica, 76 bajtów
źródło
Tr[1^...]
To sprytny sposób na znalezienie długości listy, miło!Mathematica,
1049790 bajtówHahahaha, udało mi się sprawić, żeby to działało. Nie mam pojęcia, jak korzystać z Mathematiki. XD
Wkład:
źródło
50 96
OP twierdzi, że 50 cyfr zawiera 93 liczb pierwszych, więc dokładność Sympy może być wyłączona ...?Python 3 ,
274237207194189 bajtów-37 bajtów dzięki Wheat Wizard! -14 bajtów dzięki Mr.Xcoder.
Twarde kody pierwszych 50 cyfr pi, ale ręcznie oblicza wszystko inne.
Wypróbuj online!
źródło
l=list("31415...)
powinien zaoszczędzić ~ 40 znaków. Ta zmiana pozwala zastąpićmap(str,i)
ją justi
.len(l)
R
156 156bajtówSuper ciekawe rozwiązanie. Praca nad właściwą.
Zaoszczędź 33 bajty dzięki @Giuseppe.
R (+ cyfry i gmp), 198 bajtów
Właściwe rozwiązanie. Pobiera
n
jako dane wejściowe.Używa
numbers::dropletPi(50)
do generowania pierwszych 50 miejsc po przecinku liczby pi.gsub
usuwa przecinek dziesiętny.substring
podnosi każdy możliwy podciąg (niespodzianka) pin
.Zwrócona lista jest spłaszczona i konwertowane do
gmp
„sbigz
formatu. Ten format jest wymagany do przechowywania liczb całkowitych o długości 50.unique
przyjmuje unikalne wartości tego wektora. Ten wynik zostanie zapisany wx
.Następnie sprawdzamy prymat. Jest to trudne, ponieważ istnieje mnóstwo przypadków i irytacji:
Dla wysokich
n
jest0
w pi. Prowadzi to do podciągów z wiodącym zerem.as.bigz
tworzyNA
z tym s, które muszą zostać usunięte.Podobna uwaga
"0"
spowoduje , że podciąg ulegnie awariigmp::factorize
, więc również musi zostać usunięty.Dla
n=1
,x = 3
. Co samo w sobie jest w porządku, alebigz
reprezentacja3
jest iterowalna, więcsapply
się pomylić i zgłosić 16 liczb pierwszych. W tym celu bierzemy minimalną długość wektorax
i liczbę liczb pierwszych w nim.gmp::isprime
nie wydaje się, aby niezawodnie radził sobie z dużymi liczbami w niezawodny sposób. Zamiast tego używamygmp::factorize
i sprawdzamy, czy długość wyjścia wynosi 1.W sumie usuwamy
0
iNA
zx
. Rozkładamy na czynniki wszystkiex
i sprawdzamy długość. Bieżemy pod uwagę liczbę wystąpień1
i zwracamymin(occurences, length(x))
.źródło
cumsum(c(1,1,0,1,1,4,1,0,0,3,0,0,2,7,3,1,0,3,0,0,0,0,0,0,4,1,0,6,0,3,2,0,0,0,0,0,0,4,3,3,6,0,4,8,2,5,3,6,0,5))
zamiast wektora dla 123 bajtów :)Galareta ,
5932 bajtów-27 bajtów dzięki Erikowi Outgolfer.
Wypróbuj online!
Wyjaśnienie
źródło