Hauptschalter
Input: Eine positive ganze Zahl ist, n=p^qwo pund qsind prime .
Ausgabe: Gibt das Ergebnis von ausq^p
Testfälle (rein, raus):
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
Wertung:
Dies ist Code-Golf , also kann der kürzeste Code in Bytes gewinnen! Eingabe und Ausgabe kann in jedem für Ihre Sprache geeigneten Format erfolgen.
Verwandte:
Wiederherstellen der Leistung aus der Primzahl
Wiederherstellen der Primzahl aus der Primzahl
Antworten
05AB1E , 5 Bytes
ÓOsfm
Probieren Sie es online aus!
Kommentiert:
# 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 Bytes
n=input()
p=2
while n%p:p+=1
P=p**n-1
print(n**n/P%P)**p
Probieren Sie es online aus!
Wir finden zuerst die prime \$p\$für welche \$n=p^q\$durch Inkrementieren von \$p\$bis wir einen Teiler auf \ bekommen$n\$. Danach finden wir den Exponenten \$q\$mit einem mathematischen Trick, der zuerst von Sp3000 entdeckt und in Perfect Power Logarithmen auf Anarchy Golf verwendet wurde.
Wir notieren das $$ \frac{n-1}{p-1} = \frac{p^q-1}{p-1} = 1 + p + p^2 \dots+p^{q-2}+p^{q-1}$$Arbeitsmodulo \$p-1\$haben wir \$p \equiv 1\$, also jeder von \$q\$ Die Summanden auf der rechten Seite sind gleich 1 und so: $$ \frac{n-1}{p-1} \equiv q \space \bmod (p-1)$$
Wir möchten jetzt \ extrahieren$q\$. Wir möchten dorthin gelangen, indem wir den Moduloperator %(p-1)auf der linken Seite anwenden . Dies erfordert jedoch, dass \$q<p-1\$, was nicht garantiert ist, oder wir bekommen einen anderen Wert von q%(p-1).
Glücklicherweise können wir dies mit einem weiteren Trick umgehen. Wir können \ ersetzen$n\$mit \$n^c\$und \$p\$mit \$p^c\$für eine positive Zahl \$c\$und haben noch \$n^c=(p^c)^q\$. Da der Exponent \$q\$die Beziehung ist unverändert, wir können es wie oben extrahieren, aber machen Sie es so, dass \$q<p^c-1\$. Dafür \$c=n\$ mehr als ausreichend und ist kurz für das Golfen, obwohl es größere Testfälle Zeitüberschreitung macht.
Bash + Linux-Dienstprogramme, 17
factor|dc -e?zr^p
factornimmt eine Zahl als Eingabe und faktorisiert sie. Die Ausgabe ist die Eingabenummer, gefolgt von einem Doppelpunkt, gefolgt von einer durch Abstände getrennten Liste aller Primfaktoren.- Diese Liste wird weitergeleitet, an
dcdie der folgendeeAusdruck ausgewertet wird:?liest die ganze Zeile als Eingabe. dc kann die eingegebene Nummer, gefolgt vom Doppelpunkt, nicht analysieren, daher wird sie ignoriert. Dann werden alle durch Leerzeichen getrennten Primfaktoren analysiert und auf den Stapel verschoben.zNimmt die Anzahl der Elemente auf dem Stapel (Anzahl der Primfaktoren) und schiebt diese auf den Stapelrkehrt die beiden obersten Elemente auf dem Stapel um^exponentiates und geben die erforderliche Antwortpdruckt es aus.
Probieren Sie es online aus!
MATL , 8 5 Bytes
-3 Bytes dank @LuisMendo
&YFw^
Probieren Sie es online aus!
J , 9 8 Bytes
2^~/@p:]
Probieren Sie es online aus!
2 p: ]Gibt eine Liste der Primzahlen und ihrer Exponenten zurück.^~/@Tauschen Sie dann die Argumente aus und potenzieren Sie
Python 2 , 62 Bytes
n=input()
p=2
q=-1
while n%p:p+=1
while n:n/=p;q+=1
print q**p
Probieren Sie es online aus!
C (gcc) -lm , 47 Bytes
p;f(n){for(p=1;n%++p;);p=pow(log(n)/log(p),p);}
Probieren Sie es online aus!
Brachylog , 6 Bytes
ḋ⟨l^h⟩
Probieren Sie es online aus! Bei der primären Zerlegung ḋ(wie [5, 5]) Länge l ^erstes Element h.
Eine schönere und mehr Brachylog-y-Lösung, die ein Byte länger ist:
~^ṗᵐ↔≜^
Probieren Sie es online aus! Umkehren ~^, um zwei Zahlen zu erhalten, [A,B]so dass Input = A^Bbeide Primzahlen sind ṗᵐ. Drehen Sie ↔die Liste um [B,A], finden Sie die Zahlen ≜und geben Sie sie aus B^A.
Japt , 6 Bytes
k
ÊpUg
Versuch es
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 Bytes
log(n<-scan(),p<-(b=2:n)[!n%%b][1])^p
Probieren Sie es online aus!
Meine beste Anstrengung, leider 1 Byte länger als die viel klügere R-Antwort des Xi'an , aber trotzdem im Wettbewerbsgeist zu posten.
Verwendet den einfachen Ansatz, den Primfaktor ( p<-(b=2:n)[!n%%b][1]), dann den Exponenten ( log(n,p)) zu finden und schließlich den Exponenten auf die Potenz des Faktors ( log(n,p)^p) anzuheben .
R 36 28 1 36 Bytes
Unter Verwendung der Tatsache, dass genau pPotenzen von nFaktoren sind von n^p:
sum(a<-!max(b<-2:scan())%%b)^b[a][1]
Probieren Sie es online aus!
Die Verwendung einer Funktionsdefinition ist jedoch besser (indem Sie function(m)zum Header-Teil wechseln!).
f=function(m)
sum(a<-!m%%(b<-2:m))^b[a][1]
Probieren Sie es online aus!
mit der ultimativen Verbesserung der Länge (1 Byte!), die durch Definieren von allem als Funktionsargument (in der Kopfzeile von Try It Online) erzielt wird.
f=function(m,b=2:m,a=!m%%b,d=sum(a)^b[a][1]) d
aber das entspricht nicht dem Code Golf Geist!
Haskell , 42 , 39 Bytes
f x|r<-[2..x]=[z^w|z<-r,w<-r,w^z==x]!!0
Probieren Sie es online aus!
- 3 Bytes von @xnor gespeichert
Ruby , 56 Bytes
n=gets.to_i
p=2
p+=1while n%p>0
w=p**n-1
p (n**n/w%w)**p
Port of Xnors Python 3-Antwort.
Probieren Sie es online aus! (Kopf- und Fußzeilen mit freundlicher Genehmigung von ovs .: D)
Wolfram Language (Mathematica) , 24 Bytes
#2^#&@@@FactorInteger@#&
Probieren Sie es online aus!
Gibt {q^p}eine Singleton-Liste zurück.
FactorInteger@# (* {{p,q}} *)
#2^#&@@@ (* { q^p } *)
Netzhaut , 59 Bytes
.+
*
~`(?=(__+?)\1*$)((?=(_+)(\3+)$)\4)+
_+¶$$.($.1*$($#2$*
Probieren Sie es online aus! Link enthält schnellere Testfälle. Erläuterung:
.+
*
Konvertieren Sie die Eingabe in unär.
(?=(__+?)\1*$)((?=(_+)(\3+)$)\4)+
Finden Sie zuerst den kleinsten nichttrivialen Faktor, der notwendigerweise sein wird p. Zweitens zählen Sie q, nwie oft durch den größten richtigen Faktor ersetzt werden kann. (Der richtige Faktor wird n/pbeim ersten Durchgang sein und schließlich abnehmen, 1was nicht erreicht wird, aber dies hat keinen Einfluss auf das Ergebnis.)
_+¶$$.($.1*$($#2$*
Generieren Sie eine Retina-Stufe, die nals Eingabe das Ergebnis der Multiplikation 1mit q pZeiten (in Dezimalzahlen) berechnet und somit berechnet q^p.
~`
Bewerten Sie den resultierenden Code und berechnen Sie so das gewünschte Ergebnis.
Scala , 63 Bytes
n=>2 to n find(n%_<1)map{p=>import math._;pow(log(n)/log(p),p)}
Probieren Sie es online aus!
Findet den ersten Faktor von n, der sein muss, pweil nes sich um eine Primzahl handelt, und findet dann \$\log_p(n)^p\$. Gibt eine zurück Option[Double], die a ist, Some[Double]wenn die Eingabe gültig ist.
Gelee , 6 Bytes
ÆFẎṪ*$
Probieren Sie es online aus!
Gelee , 6 Bytes
ÆFẎ*@Ɲ
Probieren Sie es online aus!
Gelee , 6 Bytes
ÆfL*ḢƊ
Probieren Sie es online aus!
Ein 5-Byter fühlt sich möglich ...
J , 8 Bytes
2^~/@p:]
Probieren Sie es online aus!
J hat eine integrierte Funktion, die die Primfaktorisierung einer bestimmten Ganzzahl in Prim-Exponenten-Form angibt. Dann geht es nur noch darum, die Potenzierung in umgekehrter Reihenfolge ( ^~) zwischen den beiden Zahlen anzuwenden .
(Scheint die gleiche zu sein wie Jonahs Antwort ; irgendwie habe ich es nicht bemerkt, bevor ich die Antwort eingereicht habe ...)
Da es auch lösbar ist mit f&.g("Unter"; Aktion g ausführen, Aktion f ausführen, dann Aktion g rückgängig machen), sind hier einige interessante:
10 Bytes
|.&.(2&p:)
2&p: Prime factorization into prime-exponent form
|. Swap the prime and exponent
&. Undo `2&p:`; evaluate the "prime" raised to "exponent"
Probieren Sie es online aus!
10 Bytes
({.##)&.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"
Probieren Sie es online aus!
JavaScript (ES7), 47 46 44 Byte
Verwendet eine rekursive Funktion, die zuerst nach dem kleinsten Divisor \ sucht$k\ge2\$von \$n\$und zählt dann, wie oft \$n\$kann durch \ geteilt werden$k\$. Das Ergebnis wird zur Potenz von \ erhoben$k\$.
n=>(k=2,g=_=>n%k?n>1&&g(k++):1+g(n/=k))()**k
Probieren Sie es online aus!
Kommentiert
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 Bytes
/ \f~#oE/
i@
Probieren Sie es online aus!
Erläuterung:
/ 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 Bytes
: 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** ;
Probieren Sie es online aus!
Funktioniert wie die C-Antwort von Noodle9 . Nimmt eine Ganzzahl und gibt eine Gleitkommazahl auf dem FP-Stapel zurück.
Wie es funktioniert
: 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 Bytes
-1 Byte dank @FryAmTheEggman
^lPQhP
Probieren Sie es online aus!
Erläuterung
^lPQhP
l # length of
PQ # prime factors of input
^ # raised to power of
hP # first element in prime factors of input
Io , 57 55 Bytes
Es wurde ein Fehler behoben, auf den @DominicvanEssen freundlicherweise hingewiesen hat
method(i,p :=2;while(i%p>0,p=p+1);i log(p)floor pow(p))
Probieren Sie es online aus!
APL (NARS2000 0.5.14),
9 Zeichen
8 Zeichen (dank Gurus in APL Orchard):
(⍴*1∘↑)π
Wie es funktioniert:
Nehmen Sie als Beispiel Eingabe 8. πzerlegt 8 in einen Vektor von Primfaktoren 2 2 2. Die Gabel ⍴*1∘↑ nimmt ein Element aus 2 2 2als Exponent, gilt dies für Länge des Vektors , 2 2 2der ist 3, zu geben 3^2 = 9.
Desmos , 61 10 + 38 = 48 Bytes
l=log_m(n)
\sum_{m=2}^{n-1}(sign(l-ceil(l))+1)l^m
Zeigen Sie es online an (beachten Sie, dass große Werte möglicherweise fehlschlagen, da Desmos mit großen Zahlen nicht gut umgehen kann).
Ich habe mich entschlossen, dies noch einmal zu überdenken, weil ich Lust hatte, mich selbst zu überlisten, und ich erinnere mich, dass dies potenzielle Ineffizienzen hatte. Ich konnte nur eine Verbesserung finden, aber sie schien für die Bearbeitung substanziell genug zu sein.
Die Eingabe erfolgt über die Variable n, die Ausgabe über die zweite Berechnung. Wenn sich die Eingabe über eine Variable falsch anfühlt, können Sie zwei Bytes für a hinzufügen n=.
Nicht schrecklich effizient Golf gespielt. Ungefähr 70% des Codes sind nur dazu bestimmt, einen Faktor zu finden, und es gibt sicherlich eine effizientere Möglichkeit, Zahlen in Desmos zu faktorisieren, aber ich habe noch keine gefunden, und Desmos fehlen integrierte Funktionen in Bezug auf Faktorisierung oder Primzahlen .
Stattdessen beobachten wir das einfach seit \$p\$und \$q\$sind prim, dann \$p*p...*p\$muss die einzige Faktorisierung von \ sein$n\$die mit ganzzahligen Werten dargestellt werden kann, weil die Liste von \$p\$s kann nicht in andere gerade Gruppen aufgeteilt werden. Daher können wir einfach durch alle ganzen Zahlen \ interagieren$m \in 2,3,...,n-1\$und finde den Wert befriedigend \$log_mn \in \mathbb{Z}\$(die Menge der ganzen Zahlen). Wir tun dies im Code mit sign(log_m(n)-ceil(log_m(n)))+1, was uns eine schöne 1 gibt, wenn sie ganzzahlig ist, und eine 0, wenn nicht. Wir multiplizieren mit log_m(n)^m, um unseren neuen Wert zu erhalten, und addieren die Ergebnisse für alle Werte 2 bis n-1, um die Antwort herauszufinden.
Schale , 5 Bytes
§^←Lp
Probieren Sie es online aus!