Znajdź liczby pierwsze w Pi

30

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 ncyfrachPi

Przykłady

Bo n=3powinniśmy szukać liczb pierwszych w [3,1,4]. Istnieją 2 Najwyżsi (3,31), więc kod powinien Wyjście 2
Na n=10pierwsze 10 cyfr [3,1,4,1,5,9,2,6,5,3]i kod powinien wyjście 12ponieważ [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 Pijeśli lubisz
Wpisy hardcoding odpowiedzi są nieważne

To jest Najkrótsza odpowiedź w bajtach wygrywa!


źródło
6
„jeśli chcesz, możesz na stałe zakodować pierwsze 50 cyfr Pi” . Pierwszy problem rozwiązany! Teraz test pierwotnej gry w golfa na liczbach całkowitych do 50 cyfr ... O_o (To niezłe wyzwanie, ale prawdopodobnie wymagane są solidne wbudowane funkcje matematyczne lub biblioteki.)
Arnauld
3
@totallyhuman Ta sekwencja jeszcze nawet w OEIS! Czas na twoje roszczenia do sławy?
Sanchises,
3
IMO zezwalające na kodowanie pierwszych 50 wartości jest szkodliwe dla tego wyzwania. Wyzwanie to składa się zasadniczo z dwóch części: 1) spróbuj skompresować pierwsze 50 wartości lub 2) faktycznie wykonać wyzwanie.
JAD,
2
Zwykle w tego rodzaju wyzwaniach, w których obliczenia stają się trudniejsze / wolniejsze / intensywnie zajmujące pamięć, wystarczy, aby program działał teoretycznie, zamiast ustawiania arbitralnego odcięcia i umożliwienia twardego kodowania.
JAD,
3
@BillSteihn Aktualizowanie reguł po kilku odpowiedziach jest niezgodne z duchem tej witryny. Czy opublikowałeś to pytanie w piaskownicy ? Bardzo wcześnie otrzymalibyście informację zwrotną, że pojawią się na stałe odpowiedzi.
Olivier Grégoire,

Odpowiedzi:

20

05AB1E ,  10  8 bajtów

-2 bajty dzięki Adnanowi (p wektoryzacja)

<žsþŒÙpO

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?

<žsþŒÙpO - implicitly push input, n
<        - decrement = n-1
 žs      - pi to that many decimal places (i.e. to n digits)
   þ     - only the digits (get rid of the decimal point)
    Œ    - all sublists
     Ù   - unique values
      p  - is prime? (vectorises) 1 if so, 0 otherwise
       O - sum
         - implicitly print the top of the stack
Jonathan Allan
źródło
<žsþŒÙpOpowinien działać przez 8 bajtów
Adnan
Ach tak pwektoryzuje dzięki!
Jonathan Allan
2
Tak! Wreszcie bardzo krótka odpowiedź na golfa, którą naprawdę rozumiem! : D
Fabian Röling
11

Mathematica, 76 bajtów

Tr[1^Union@Select[FromDigits/@Subsequences@#&@@RealDigits[Pi,10,#],PrimeQ]]&
J42161217
źródło
Och, nie fair, nie znam golfa Mathematica. : P (+1)
całkowicie ludzki,
@totallyhuman Opublikowaliśmy to w tym samym czasie. to takie dziwne!
J42161217,
Grałem w golfa, używając niektórych sztuczek syntaktycznych, ale zachowałem funkcje, z których wcześniej korzystałem. Mam nadzieję, że nie masz nic przeciwko.
całkowicie ludzki
Tr[1^...]To sprytny sposób na znalezienie długości listy, miło!
numbermaniac
6

Mathematica, 104 97 90 bajtów

Length@DeleteDuplicates@Select[FromDigits/@Subsequences@First@RealDigits[Pi,10,#],PrimeQ]&

Hahahaha, udało mi się sprawić, żeby to działało. Nie mam pojęcia, jak korzystać z Mathematiki. XD

Wkład:

[50]
całkowicie ludzki
źródło
1
opublikowałeś kilka sekund przede mną. a nasze odpowiedzi są bardzo podobne! +1
J42161217,
Czy jesteś pewien co do liczb, które właśnie opublikowałeś (sprawdź dokładnie zaokrąglenie cyfr) Widzę nieco inne wyniki przy użyciu Pythona i sympii
Jonathan Allan
@JonathanAllan 50 96OP twierdzi, że 50 cyfr zawiera 93 liczb pierwszych, więc dokładność Sympy może być wyłączona ...?
totalnie ludzki,
@JonathanAllan Czy Sympy używa probabilistycznego lub deterministycznego testu pierwszeństwa? (To samo pytanie dla PrimeQ Mathematiki)
Arnauld
@Arnauld dobry punkt, nie jestem pewien.
Jonathan Allan
3

Python 3 , 274 237 207 194 189 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.

x=int(input());l="31415926535897932384626433832795028841971693993751"[:x]
print(sum(all(i%m for m in range(2,i))for i in{int(i)for w in range(x)for i in[l[j:j-~w]for j in range(x-w)]}-{1}))

Wypróbuj online!

całkowicie ludzki
źródło
l=list("31415...)powinien zaoszczędzić ~ 40 znaków. Ta zmiana pozwala zastąpić map(str,i)ją just i.
AShelly,
195 bajtów poprzez usunięcie jakiegoś dziwnego kodu.
Mr. Xcoder,
194 bajtów , ogłaszająclen(l)
Pan Xcoder
1

R 156 156 bajtów

cat(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))[scan()])

Super ciekawe rozwiązanie. Praca nad właściwą.

Zaoszczędź 33 bajty dzięki @Giuseppe.

R (+ cyfry i gmp), 198 bajtów

function(n,x=unique(gmp::as.bigz(unlist(sapply(1:n,function(x)substring(gsub("[.]","",numbers::dropletPi(50)),x,x:n))))))min(length(x),sum(sapply(sapply(x[x>0&!is.na(x)],gmp::factorize),length)==1))

Właściwe rozwiązanie. Pobiera njako dane wejściowe.

Używa numbers::dropletPi(50)do generowania pierwszych 50 miejsc po przecinku liczby pi. gsubusuwa przecinek dziesiętny. substringpodnosi każdy możliwy podciąg (niespodzianka) pi n.

Zwrócona lista jest spłaszczona i konwertowane do gmp„s bigzformatu. Ten format jest wymagany do przechowywania liczb całkowitych o długości 50. uniqueprzyjmuje unikalne wartości tego wektora. Ten wynik zostanie zapisany w x.

Następnie sprawdzamy prymat. Jest to trudne, ponieważ istnieje mnóstwo przypadków i irytacji:

  • Dla wysokich njest 0w pi. Prowadzi to do podciągów z wiodącym zerem. as.bigztworzy NAz tym s, które muszą zostać usunięte.

  • Podobna uwaga "0"spowoduje , że podciąg ulegnie awarii gmp::factorize, więc również musi zostać usunięty.

  • Dla n=1, x = 3. Co samo w sobie jest w porządku, ale bigzreprezentacja 3jest iterowalna, więc sapplysię pomylić i zgłosić 16 liczb pierwszych. W tym celu bierzemy minimalną długość wektora xi liczbę liczb pierwszych w nim.

  • gmp::isprimenie wydaje się, aby niezawodnie radził sobie z dużymi liczbami w niezawodny sposób. Zamiast tego używamy gmp::factorizei sprawdzamy, czy długość wyjścia wynosi 1.

W sumie usuwamy 0i NAz x. Rozkładamy na czynniki wszystkie xi sprawdzamy długość. Bieżemy pod uwagę liczbę wystąpień 1i zwracamy min(occurences, length(x)).

JAD
źródło
tutaj jesteś! Zobaczmy teraz, czy ktoś może outgolf z bardziej interesującym rozwiązaniem. może być tobą!
użyj 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 :)
Giuseppe,
@Giuseppe Nice one. Ta „kompresja” z pewnością przebije każde legalne rozwiązanie.
JAD,
Myślę, że jest to niemożliwe w R bez twardego kodowania lub wprowadzenia innego pakietu, ponieważ R ma tylko 32-bitowe liczby całkowite, co z pewnością nie będzie reprezentować 50-cyfrowej liczby całkowitej.
Giuseppe,
1
Tak, mogę jeszcze trochę o tym pomyśleć. 82 zaszyfrowanych bajtów
Giuseppe,
0

Galareta , 59 32 bajtów

-27 bajtów dzięki Erikowi Outgolfer.

“!⁶⁷¬,6½ạEC.wʠ€Ẉ!+Ẉfṭ¡’Ṿḣ³ẆVQÆPS

Wypróbuj online!

Wyjaśnienie

“...’Ṿḣ³ẆVQÆPS

“...’           compressed string that evaluates to first 50 digits of pi (314159...)
     Ṿ          uneval; stringify
      ḣ³        first n characters of the string where n is the first command-line argument
        Ẇ       all sublists
         V      convert all elements to integers
          Q     deduplicate
           ÆP   convert all prime elements to 1 and others to 0
             S  sum
całkowicie ludzki
źródło
Dlaczego spamujesz to z odpowiedziami?
Zacharý
Ponieważ nikt inny nie odpowiadał, a ja i tak uderzyłem w czapkę przedstawiciela. : P
totalnie ludzki,