Odzyskaj liczbę pierwszą z podstawowej mocy

13

Definicja : potęga pierwsza jest liczbą naturalną, którą można wyrazić w postaci p n, gdzie p jest liczbą pierwszą, a n jest liczbą naturalną.

Zadanie : Biorąc pod uwagę siłę pierwszą p n > 1, zwróć liczbę pierwszą p.

Przypadki testowe :

input output
9     3
16    2
343   7
2687  2687
59049 3

Punktacja : To jest golf . Najkrótsza odpowiedź w bajtach wygrywa.

code-golf arithmetic primes king-of-the-hill python board-game code-golf number subsequence code-golf ascii-art code-golf array-manipulation decision-problem grid fastest-algorithm logic-gates logic code-golf cards code-golf rational-numbers code-golf math number sequence code-golf array-manipulation integer code-golf number array-manipulation code-golf number sequence decision-problem code-golf ascii-art number code-challenge sequence arithmetic sorting code-golf date fastest-algorithm code-golf string number random combinatorics code-golf combinatorics code-golf ascii-art base-conversion code-golf array-manipulation code-golf string code-golf string number arithmetic code-golf kolmogorov-complexity code-golf string array-manipulation json code-golf puzzle-solver code-golf binary graph-theory code-golf arithmetic haskell code-golf string cipher code-golf code-golf string parsing alphabet code-golf string code-golf ascii-art code-golf string number code-golf string balanced-string Leaky Nun
źródło
1
Może nbyć 1?
user202729,
@ user202729: W czwartym przypadku testowym n = 1.
Emigna,
15
Może trudniej byłoby zdobyć część mocy zamiast części głównej. W tej chwili jest to po prostu „Uzyskaj najniższy czynnik, który nie jest równy 1”
Jo King

Odpowiedzi:

13

Język programowania Szekspira , 209 207 bajtów

T.Ajax,.Page,.Act I:.Scene I:.[Enter Ajax and Page]Ajax:Listen tothy!Page:You cat!Scene V:.Page:You be the sum ofyou a cat!Be the product ofthe quotient betweenI you you worse I?If soLet usScene V.Open heart

Wypróbuj online!

(I/you)*you<Ijest krótszy niż I%you>0w SPL.

użytkownik202729
źródło
1
Właściwe narzędzie do pracy.
Jeremy Weirich,
7

Java 8, 46 39 37 bajtów

n->{int r=1;for(;n%++r>0;);return r;}

-7 bajtów pośrednio dzięki @Tsathoggua .
-2 bajty dzięki JoKing

Wypróbuj online.

Wyjaśnienie:

n->{               // Method with integer as both parameter and return-type
  int r=1;         //  Start the result-integer `r` at 1
  for(;n%++r>0;);  //  Increase `r` by 1 before every iteration with `++r`
                   //  and loop until `n` is divisible by `r`
  return r;}       //  After the loop, return `r` as result
Kevin Cruijssen
źródło
Czy po odpowiedzi Luisa Mendo w python3 można napisać, n->{for(int i=1;++i<=n;)if(n%i<1)return i;}aby uzyskać 43 znaki? (Nie mówię po Javie.)
Tsathoggua,
@Tsathoggua W tej chwili nie, ponieważ metody Java zawsze muszą mieć zwrot. n->{for(int i=1;++i<=n;)if(n%i<1)return i;return n;}działałby, ale niestety jest dłuższy. Jednak Java może mieć pojedynczy zwrot w nieskończonych pętlach, co faktycznie oszczędza bajty, więc dziękuję! n->{for(int i=1;;)if(n%++i<1)return i;}. Ponieważ ibędzie nostatecznie (jak w przypadku testu 2687) i n%n==0The i<=nnie jest wymagane w tym przypadku.
Kevin Cruijssen
1
Co powiesz na 37 bajtów . Nie znam się na Javie, by sprawdzić, czy można grać w golfa
Jo King
@JoKing Nie widzę już nic do gry w golfa, więc dziękuję za -2.
Kevin Cruijssen
5

Python 3 , 36 35 bajtów

-1 bajt dzięki Mathmandan

f=lambda n,x=2:n%x and f(n,x+1)or x

Wypróbuj online!

Funkcja rekurencyjna, w której pierwszy czynnik jest większy niż 1

Jo King
źródło
1
Ładny. Można (zazwyczaj) zapisać bajt, jeśli zastąpi if/elsesię and/or. Podobnie jak f=lambda n,x=2:n%x and f(n,x+1)or x.
matmandan
4

MATL , 4 3 bajty

Yfu

Wypróbuj online!

Wyjaśnienie:

       % Implicit input:      [59049]
Yf     % Prime factorization: [3 3 3 3 3 3 3 3 3 3]
  u    % Unique elements:     [3]
       % Implicit output
Stewie Griffin
źródło
1
Bardzo fajna poprawa! Chciałbym jeszcze raz głosować :-)
Luis Mendo,
4

Biała spacja , 80 61 60 bajtów

[S S T  T   N
_Push_-1][S S S N
_Push_0][T  N
T   T   _Read_STDIN_as_number][N
S S N
_Create_Label_LOOP][S S S T N
_Push_1][T  S S T   _Subtract][S N
S _Duplicate][S S S N
_Push_0][T  T   T   _Retrieve][S N
T   _Swap][T    S T T   _Modulo][N
T   T   N
_If_0_Jump_to_Label_LOOP][S S T T   N
_Push_-1][T S S N
_Multiply][T    N
S T _Print_as_number]

-20 bajtów dzięki @JoKing .

Dodane litery S(spacja), T(tab) i N(nowa linia) tylko jako wyróżnienia.
[..._some_action]dodano tylko jako wyjaśnienie.

Wypróbuj online (tylko z surowymi spacjami, tabulatorami i nowymi wierszami).

Objaśnienie w pseudo-kodzie:

Integer n = STDIN as integer
Integer i = -1
Start LOOP:
  i = i - 1
  if(n modulo-i is negative)
    Go to next iteration of LOOP
  else
    i = i * -1
    Print i
    Exit with error: No exit defined

Przykładowy przebieg: input = 9

Command   Explanation                    Stack        Heap     STDIN    STDOUT    STDERR

SSTTN     Push -1                        [-1]
SSSN      Push 0                         [-1,0]
TNTT      Read STDIN as integer          [-1]         {0:9}    9
NSSN      Create Label_LOOP              [-1]         {0:9}
 SSSTN    Push 1                         [-1,1]       {0:9}
 TSST     Subtract top two (-1-1)        [-2]         {0:9}
 SNS      Duplicate top (-2)             [-2,-2]      {0:9}
 SSSN     Push 0                         [-2,-2,0]    {0:9}
 TTT      Retrieve                       [-2,-2,9]    {0:9}
 SNT      Swap top two                   [-2,9,-2]    {0:9}
 TSTT     Modulo top two (9%-2)          [-2,-1]      {0:9}
 NTSN     If neg.: Jump to Label_LOOP    [-2]         {0:9}

 SSTTN    Push -1                        [-2,-1]      {0:9}
 TSST     Subtract top two (-2-1)        [-3]         {0:9}
 SNS      Duplicate top (-2)             [-3,-3]      {0:9}
 SSSN     Push 0                         [-3,-3,0]    {0:9}
 TTT      Retrieve                       [-3,-3,9]    {0:9}
 SNT      Swap top two                   [-3,9,-3]    {0:9}
 TSTT     Modulo top two (9%-3)          [-3,0]       {0:9}
 NTSN     If neg.: Jump to Label_LOOP    [-3]         {0:9}
 SSTTN    Push -1                        [-3,-1]      {0:9}
 TSSN     Multiply top two (-3*-1)       [3]          {0:9}
 TNST     Print as integer               []           {0:9}             3
                                                                                  error

Program zatrzymuje się z błędem: nie znaleziono wyjścia.

Kevin Cruijssen
źródło
1
Potrzebujesz i == nczeku? n%nw każdym razie byłoby 0
Jo King
@JoKing Ah, oczywiście. Dzięki, 19 bajtów zapisanych właśnie tam. :)
Kevin Cruijssen
Czy możesz zapętlić tylko, jeśli nie, n%ii wywołać wydruk później?
Jo King
1
@JoKing Jestem pewien, że nie. Białe znaki nie mają tak naprawdę pętli, tylko przeskakują do etykiet. Jedyne trzy opcje, które mam, to: 1. bezwarunkowo przejść do określonej wytwórni; 2. przeskocz do określonej etykiety, jeśli górna część stosu ma wartość 0; 3. przeskocz do określonej etykiety, jeśli górna część stosu jest ujemna. Niestety nie ma „skoku do etykiety, jeśli pozytywne”, aby kontynuować pętlę. Mógłbym to osiągnąć, mnożąc przez -1, zanim sprawdzę wartość ujemną, ale wątpię, aby była krótsza.
Kevin Cruijssen
1
Próbowałem to zrobić z ujemnym modułem i skończyło się na <s> 62 </s> 60 bajtach (yay). Okazuje się, że nie można przechowywać pod ujemnymi adresami sterty (choć 0 zapisało kilka bajtów)
Jo King
4

Oktawa , 16 bajtów

@(x)factor(x)(1)

Wypróbuj online!

Wyjaśnienie:

@(x)              % Anonymous function taking x as input
    factor(x)     % Prime factorization
             (1)  % Get the first element

Lub: 

@(x)max(factor(x))  % the makeup of makeup artists
Stewie Griffin
źródło
1
+1 dla maksymalnego współczynnika
Brain Guider
3

Funky , 30 bajtów

n=>fori=2n>i i++if1>n%i breaki

Wypróbuj online!

ATaco
źródło
0==1>myślę, że może być .
Kevin Cruijssen
2

Galaretka , 3 bajty

ÆfḢ

Wypróbuj online!

ÆfṪ, ÆfXmogą być również poważnie konkurującymi funkcjami.
ÆfQmoże być poważnie konkurującym pełnym programem.

Erik the Outgolfer
źródło
2

Dalej (gforth) , 34 bajty

: f 1 begin 1+ 2dup mod 0= until ;

Wypróbuj online!

Wyjaśnienie

  1. Iteruj liczby całkowite zaczynając od 2
  2. Zatrzymaj się i wróć, gdy znajdziesz taki, który dzieli n bez reszty

Objaśnienie kodu

: f               \ Define a new word
  1               \ place a 1 on the stack (to use as a counter/index)
  begin           \ start indefinite loop
    1+ 2dup       \ increment counter and duplicate counter and prime power
    mod           \ calculate power % index
  0= until        \ end the loop if modulus is 0 (no remainder)
;                 \ end word definition
reffu
źródło
1

Neim , 1 bajt

𝐔

Wypróbuj online!

Okx
źródło
U + 1D414 jest jednym znakiem, ale w UTF-8 i UTF-16 jest reprezentowany przez 4 bajty.
Ruud Helderman
1
@RuudHelderman Poprawnie, ale nie ma tego w UTF-8 ani UTF-16.
Okx
1
@RuudHelderman Możesz zobaczyć stronę kodową Neima .
JungHwan Min
@JungHwanMin Thanks; przeglądając wcześniejsze wypowiedzi Neima Okxa, zauważyłem, że moja lekko ignorancka reakcja nie była pierwsza. Sprytna funkcja, ale daleka od oczywistości; uzasadnia wyjaśnienie (tak jak tutaj ). Cytując informacje o znaczniku code-golf : „O ile pytanie nie zostanie określone według znaków, jest ono oceniane według bajtów. Jeśli nie określa kodowania znaków, które ma być stosowane do oceniania, odpowiedzi, które używają punktów kodu Unicode spoza zakresu od 0 do 255, powinny podaj zastosowane kodowanie. ”
Ruud Helderman
@RuudHelderman zgodnie z meta konsensusem , jeśli odpowiedź nie określa kodowania, domyślnie jest to kodowanie domyślne języka. Jeśli to nie istnieje, to jest to UTF-8. W tym przypadku Neim ma zdefiniowane domyślne kodowanie, więc zakłada się, że jest to kodowanie odpowiedzi, bez konieczności odpowiadania przez odpowiadającego.
JungHwan Min
1

Mathematica, 17 bajtów

Divisors[#][[2]]&

Drugi najmniejszy dzielnik.

dla Moniki
źródło
1

R , 32 26 bajtów

@Giuseppe z inną logiką i krótszym rozwiązaniem:

(x=2:(n=scan()))[!n%%x][1]

Wypróbuj online!

Oryginalny:

numbers::primeFactors(scan())[1]

Wypróbuj online!

Jest to oczywiście znacznie lepszy port rozwiązania 05AB1E .

ngm
źródło
0

PowerShell , 31 bajtów

param($a)(2..$a|?{!($a%$_)})[0]

Wypróbuj online!

Konstruuje zakres od 2do wejścia $a, wyciąga te elementy where( ?), %wynikiem operacji modulo jest zero !(...)(tzn. Te, które są dzielnikami $a), a następnie przyjmuje najmniejszy z [0]nich. Pozostaje w przygotowaniu, wynik jest domyślny.

AdmBorkBork
źródło
0

Perl 6 , 22 bajtów

{grep($_%%*,2..$_)[0]}

Wypróbuj online!

Anonimowy blok kodu, który filtruje czynniki z zakresu 2 do danych wejściowych i zwraca pierwszy. Próbowałem ^$zapisać 2 bajty, ale to nie zadziałało w przypadku, gdy dane wejściowe były pierwsze.

Jo King
źródło
0

Visual Basic .NET (.NET Framework v4.5), 123 71 bajtów

-52 bajty dzięki @Jo King

Function A(n)
For i=n To 2 Step-1
A=If(n Mod i=0,i,A)
Next
End Function

Wypróbuj online!

Nie golfowany:

Function A(input As Long) As Long
    For i = input To 2 Step -1
        A = If (input Mod i = 0, i, A)
    Next
End Function

Wyjaśnienie:

Do iwyszukania pętli wstecz od pierwszego numeru i wyszukuje wszystkie numery, które dzielą go równomiernie. Ponieważ cofamy się, najmniejsze są przechowywane w vairable A.

VB daje ci dowolną zmienną, która pasuje do nazwy twojej funkcji (w moim przypadku, A). Pod koniec wykonywania funkcji zwracana jest wartość w tej zmiennej (z wyjątkiem jawnej Returninstrukcji).

Brian J.
źródło
1
W ogóle nie potrzebujesz kontroli wstępnej. Najmniejszy czynnik z liczby (inny niż 1) jest gwarantowany jako liczba pierwsza, w przeciwnym razie byłby czynnik mniejszy
Jo King
@JoKing D'oh! Oczywiście nie mogę uwierzyć, że mi tego brakowało. Dzięki!
Brian J