Prime Power Switch
Dane wejściowe: dodatnia liczba całkowita, n=p^qgdzie pi qsą liczbą pierwszą .
Wyjście: wypisuje wynikq^p
Przypadki testowe (wejście, wyjście):
4, 4
8, 9
25, 32
27, 27
49, 128
121, 2048
125, 243
343, 2187
1331, 177147
3125, 3125,
16807, 78125,
823543, 823543
161051, 48828125
19487171, 1977326743
Punktacja:
To jest code-golf , więc może wygrać najkrótszy kod w bajtach! Dane wejściowe i wyjściowe mogą być w jakimkolwiek rozsądnym formacie odpowiednim dla Twojego języka.
Powiązane:
Odzyskaj siłę główną od siły głównej Odzyskaj moc
główną od siły głównej
Odpowiedzi
05AB1E , 5 bajtów
ÓOsfm
Wypróbuj online!
Skomentował:
# implicit input 25
Ó # prime factor exponents [0, 0, 2]
O # sum 2
s # swap (with input) 25, 2
f # unique prime factors [5], 2
m # power [32]
Python 2 , 56 bajtów
n=input()
p=2
while n%p:p+=1
P=p**n-1
print(n**n/P%P)**p
Wypróbuj online!
Najpierw znajdujemy liczbę pierwszą \$p\$dla którego \$n=p^q\$zwiększając \$p\$dopóki nie otrzymamy dzielnika na \$n\$. Następnie znajdujemy wykładnik \$q\$z matematyczną sztuczką odkrytą po raz pierwszy przez Sp3000 i wykorzystaną w logarytmach mocy Perfect na Anarchy Golf.
Zauważamy to $$ \frac{n-1}{p-1} = \frac{p^q-1}{p-1} = 1 + p + p^2 \dots+p^{q-2}+p^{q-1}$$Praca modulo \$p-1\$, mamy \$p \equiv 1\$, więc każdy z \$q\$ szczyty po prawej stronie są równe 1, a więc: $$ \frac{n-1}{p-1} \equiv q \space \bmod (p-1)$$
Chcielibyśmy teraz wyodrębnić \$q\$. Chcielibyśmy się tam dostać, stosując operator modułu %(p-1)po lewej stronie. Ale to wymaga tego \$q<p-1\$, co nie jest gwarantowane lub otrzymamy inną wartość q%(p-1).
Na szczęście możemy to obejść jeszcze jedną sztuczką. Możemy wymienić \$n\$z \$n^c\$i \$p\$z \$p^c\$dla jakiejś liczby dodatniej \$c\$i nadal mam \$n^c=(p^c)^q\$. Ponieważ wykładnik \$q\$ich relacja jest niezmieniona, możemy ją wyodrębnić jak wyżej, ale sprawimy, że \$q<p^c-1\$. W tym celu \$c=n\$ więcej niż wystarcza i jest krótka do gry w golfa, chociaż powoduje przekroczenie limitu czasu dla większych przypadków testowych.
Narzędzia Bash + Linux, 17
factor|dc -e?zr^p
factorprzyjmuje liczbę jako dane wejściowe i rozkłada ją na czynniki. Dane wyjściowe to liczba wejściowa, po której następuje dwukropek, po którym następuje rozdzielona odstępami lista wszystkich czynników pierwszych.- Ta lista jest przesyłana potokiem, do
dcktórego ocenia następująceexpression:?czyta cały wiersz jako wejście. dc nie może przeanalizować numeru wejściowego, po którym następuje dwukropek, więc go ignoruje. Następnie analizuje wszystkie rozdzielone spacjami czynniki pierwsze i umieszcza je na stosie.zpobiera liczbę elementów na stosie (liczbę czynników pierwszych) i odkłada ją na stosrodwraca dwa górne elementy na stosie^potęguje, podając wymaganą odpowiedźpdrukuje to.
Wypróbuj online!
MATL , 8 5 bajtów
-3 bajty dzięki @LuisMendo
&YFw^
Wypróbuj online!
J , 9 8 bajtów
2^~/@p:]
Wypróbuj online!
2 p: ]zwraca listę liczb pierwszych i ich wykładników.^~/@następnie zamień argumenty i potęguj
Python 2 , 62 bajty
n=input()
p=2
q=-1
while n%p:p+=1
while n:n/=p;q+=1
print q**p
Wypróbuj online!
C (gcc) -lm , 47 bajtów
p;f(n){for(p=1;n%++p;);p=pow(log(n)/log(p),p);}
Wypróbuj online!
Brachylog , 6 bajtów
ḋ⟨l^h⟩
Wypróbuj online! Na pierwszym rozkładzie ḋ(jak [5, 5]) długość l ^pierwszego elementu h.
Ładniejsze i bardziej Brachylog-y rozwiązanie, czyli o bajt dłuższe:
~^ṗᵐ↔≜^
Wypróbuj online! Odwróć, ~^aby uzyskać dwie liczby, [A,B]tak aby Input = A^Bobie były liczbą pierwszą ṗᵐ. Odwróć ↔listę, aby [B,A]znaleźć liczby ≜i wyniki B^A.
Japt , 6 bajtów
k
ÊpUg
Spróbuj
k\nÊpUg :Implicit input of integer U
k :Prime factors
\n :Reassign to U
Ê :Length
p :Raised to the power of
Ug :First element of U
R , 37 bajtów
log(n<-scan(),p<-(b=2:n)[!n%%b][1])^p
Wypróbuj online!
Mój najlepszy wysiłek, niestety o 1 bajt dłużej niż znacznie sprytniejsza odpowiedź R Xi'ana , ale i tak publikowanie w duchu rywalizacji.
Stosuje proste podejście polegające na znalezieniu czynnika pierwszego ( p<-(b=2:n)[!n%%b][1]), następnie wykładnika ( log(n,p)) i na końcu podniesienie wykładnika do potęgi współczynnika ( log(n,p)^p).
R 36 28 1 36 bajtów
Wykorzystując fakt, że dokładnie ppotęgi nsą czynnikami n^p:
sum(a<-!max(b<-2:scan())%%b)^b[a][1]
Wypróbuj online!
ale użycie definicji funkcji działa lepiej (przechodząc function(m)do części nagłówka!)
f=function(m)
sum(a<-!m%%(b<-2:m))^b[a][1]
Wypróbuj online!
z ostateczną poprawą długości (1 bajt!), uzyskaną przez zdefiniowanie wszystkiego jako argumentu funkcji (w nagłówku Try It Online).
f=function(m,b=2:m,a=!m%%b,d=sum(a)^b[a][1]) d
ale to nie jest zgodne z duchem golfa!
Haskell , 42 , 39 bajtów
f x|r<-[2..x]=[z^w|z<-r,w<-r,w^z==x]!!0
Wypróbuj online!
- 3 bajty zapisane przez @xnor
Ruby , 56 bajtów
n=gets.to_i
p=2
p+=1while n%p>0
w=p**n-1
p (n**n/w%w)**p
Odpowiedź Port of xnor w Pythonie 3.
Wypróbuj online! (nagłówki i stopki dzięki uprzejmości ovs.: D)
Język Wolfram (Mathematica) , 24 bajty
#2^#&@@@FactorInteger@#&
Wypróbuj online!
Zwroty {q^p}, lista singletonów.
FactorInteger@# (* {{p,q}} *)
#2^#&@@@ (* { q^p } *)
Retina , 59 bajtów
.+
*
~`(?=(__+?)\1*$)((?=(_+)(\3+)$)\4)+
_+¶$$.($.1*$($#2$*
Wypróbuj online! Link zawiera szybsze przypadki testowe. Wyjaśnienie:
.+
*
Konwertuj dane wejściowe na jednoargumentowe.
(?=(__+?)\1*$)((?=(_+)(\3+)$)\4)+
Najpierw znajdź najmniejszy nietrywialny czynnik, który koniecznie będzie p. Po drugie, policzyć liczbę razy q, że nmożna zastąpić swoim największym właściwego czynnika. (Właściwy współczynnik będzie n/pprzy pierwszym przejściu i ostatecznie spadnie, do 1którego nie ma sobie równych, ale nie ma to wpływu na wynik).
_+¶$$.($.1*$($#2$*
Wygeneruj etap Retina, który przyjmuje njako dane wejściowe i oblicza (dziesiętnie) wynik mnożenia 1przez q prazy, w ten sposób obliczając q^p.
~`
Oceń wynikowy kod, obliczając w ten sposób pożądany wynik.
Scala , 63 bajty
n=>2 to n find(n%_<1)map{p=>import math._;pow(log(n)/log(p),p)}
Wypróbuj online!
Znajduje pierwszy czynnik n, który musi być, pponieważ njest potęgą pierwszą, a następnie znajduje \$\log_p(n)^p\$. Zwraca wartość Option[Double]a, Some[Double]jeśli dane wejściowe są prawidłowe.
Galaretka , 6 bajtów
ÆFẎṪ*$
Wypróbuj online!
Galaretka , 6 bajtów
ÆFẎ*@Ɲ
Wypróbuj online!
Galaretka , 6 bajtów
ÆfL*ḢƊ
Wypróbuj online!
Wydaje się, że 5-byter ...
J , 8 bajtów
2^~/@p:]
Wypróbuj online!
J ma wbudowaną funkcję, która podaje na czynniki pierwsze faktoryzację danej liczby całkowitej w postaci wykładnika-liczby pierwszej. Wtedy wystarczy zastosować potęgowanie w odwrotnej kolejności ( ^~) między dwiema liczbami.
(Zdarza się, że jest taka sama jak odpowiedź Jonah ; jakoś nie zauważyłem, zanim przedstawiłem odpowiedź ...)
Ponieważ można go również rozwiązać za pomocą f&.g("Under"; wykonaj akcję g, wykonaj akcję f, a następnie cofnij akcję g), oto kilka interesujących:
10 bajtów
|.&.(2&p:)
2&p: Prime factorization into prime-exponent form
|. Swap the prime and exponent
&. Undo `2&p:`; evaluate the "prime" raised to "exponent"
Wypróbuj online!
10 bajtów
({.##)&.q:
q: Prime factorization into plain list of primes
{. Head (prime)
# Copies of
# Length (exponent)
{.## Essentially swap the role of prime and exponent
&. Undo `q:`; product of all "primes"
Wypróbuj online!
JavaScript (ES7), 47 46 44 bajty
Używa funkcji rekurencyjnej, która najpierw szuka najmniejszego dzielnika \$k\ge2\$z \$n\$a potem liczy ile razy \$n\$można podzielić przez \$k\$. Wynik jest podnoszony do potęgi \$k\$.
n=>(k=2,g=_=>n%k?n>1&&g(k++):1+g(n/=k))()**k
Wypróbuj online!
Skomentowano
n => ( // main function taking n
k = 2, // start with k = 2
g = _ => // g is a recursive function ignoring its input
n % k ? // if k is not a divisor of n:
// this point of the code is reached during the first step
// of the algorithm; but it's also reached on the last
// iteration when n = 1, which is why ...
n > 1 && // ... we test whether n is greater than 1 ...
g(k++) // ... in which case we do a recursive call with k + 1
: // else (k has been found):
1 + // add 1 to the final result
g(n /= k) // and do a recursive call with n / k
)() // initial call to g
** k // raise the result to the power of k
Alice , 13 bajtów
/ \f~#oE/
i@
Wypróbuj online!
Wyjaśnienie:
/ Switch to Ordinal mode
i Push the input as a string
\ Switch to Cardinal mode
f Pop n, implicitly convert n to an integer,
and push the prime factors of n as pairs of prime and exponent
~ Swap the top two elements of the stack
# Skip the next command
E Pop y, pop x. If y is non-negative, push x ^ y
/ Switch to Ordinal mode
o Pop s, then output s as a string.
~ Swap the top two elements of the stack.
\ Switch to Cardinal mode
@ Terminate the program
Forth (gforth) , 85 bajtów
: f dup 2 do dup i mod 0= if i leave then loop tuck swap s>f fln s>f fln f/ s>f f** ;
Wypróbuj online!
Działa jak odpowiedź C z Noodle9 . Pobiera liczbę całkowitą i zwraca liczbę zmiennoprzecinkową na stosie FP.
Jak to działa
: f ( n -- float )
dup 2 do \ loop from i = 2..n-1
dup i mod 0= if \ if n % i == 0
i leave \ ( n p ) we found p; leave the loop
then \ end if
loop \ end loop
tuck swap \ ( p p n )
s>f fln s>f fln \ ( p F:ln(n) F:ln(p) )
f/ \ ( p F:q ) q = ln(n)/ln(p)
s>f f** \ ( F:q**p )
;
Pyth , 7 6 bajtów
-1 bajt dzięki @FryAmTheEggman
^lPQhP
Wypróbuj online!
Wyjaśnienie
^lPQhP
l # length of
PQ # prime factors of input
^ # raised to power of
hP # first element in prime factors of input
Io , 57 55 bajtów
Naprawiono błąd wskazany przez @DominicvanEssen
method(i,p :=2;while(i%p>0,p=p+1);i log(p)floor pow(p))
Wypróbuj online!
APL (NARS2000 0.5.14),
9 znaków
8 znaków (dzięki guru w APL Orchard):
(⍴*1∘↑)π
Jak to działa:
Weźmy jako przykład wejście 8. πrozkłada 8 na wektor czynników pierwszych 2 2 2. Widelec ⍴*1∘↑ trwa jeden element ze 2 2 2jako wykładnik, dotyczy to długość wektora 2 2 2, która jest 3, co daje 3^2 = 9.
Desmos , 61 10 + 38 = 48 bajtów
l=log_m(n)
\sum_{m=2}^{n-1}(sign(l-ceil(l))+1)l^m
Zobacz to online (pamiętaj, że duże wartości mogą się nie udać, ponieważ Desmos nie obsługuje dobrze dużych liczb)
Postanowiłem wrócić do tego tematu, ponieważ miałem ochotę prześcignąć samego siebie i pamiętam, że miało to potencjalne nieefektywności. Udało mi się znaleźć tylko jedno ulepszenie, ale wydawało się wystarczająco istotne dla edycji.
Wejście następuje przez zmienną n, wyjście poprzez drugie obliczenie. Jeśli pobieranie danych wejściowych za pośrednictwem zmiennej wydaje się niewłaściwe, możesz dodać dwa bajty do pliku n=.
Nie grał strasznie wydajnie w golfa. Około 70% kodu jest poświęcone po prostu znalezieniu jednego czynnika i na pewno istnieje bardziej skuteczny sposób na rozłożenie liczb w Desmos, ale jeszcze takiego nie znalazłem, a Desmos nie ma wbudowanych funkcji związanych z faktoryzacją lub liczbami pierwszymi .
Zamiast tego po prostu obserwujemy, że skoro \$p\$i \$q\$są liczbą pierwszą, to \$p*p...*p\$musi być jedyną faktoryzacją \$n\$które można przedstawić za pomocą wartości całkowitych, ponieważ lista \$p\$nie można podzielić na żadne inne parzyste grupy. Dlatego możemy po prostu przeprowadzić interakcję przez wszystkie liczby całkowite \$m \in 2,3,...,n-1\$i znajdź satysfakcjonującą wartość \$log_mn \in \mathbb{Z}\$(zbiór liczb całkowitych). Robimy to w kodzie za pomocą sign(log_m(n)-ceil(log_m(n)))+1, co daje nam ładną 1, gdy całkowite i 0, gdy nie. Mnożymy przez, log_m(n)^maby otrzymać nową wartość, i sumujemy wyniki dla wszystkich wartości od 2 do n-1, aby wyodrębnić odpowiedź.
Łuska , 5 bajtów
§^←Lp
Wypróbuj online!