Prime Power Switch
การป้อนข้อมูล:เป็นจำนวนเต็มบวกn=p^qที่pและqมีความสำคัญ
เอาต์พุต:แสดงผลลัพธ์ของq^p
กรณีทดสอบ (เข้า, ออก):
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
การให้คะแนน:
นี่คือรหัสกอล์ฟดังนั้นรหัสที่สั้นที่สุดในหน่วยไบต์อาจชนะ! อินพุตและเอาต์พุตอาจอยู่ในรูปแบบที่เหมาะสมกับภาษาของคุณ
ที่เกี่ยวข้อง:
Recover the power from the prime power
Recover the prime from the prime power
คำตอบ
05AB1E , 5 ไบต์
ÓOsfm
ลองออนไลน์!
แสดงความคิดเห็น:
# 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 ไบต์
n=input()
p=2
while n%p:p+=1
P=p**n-1
print(n**n/P%P)**p
ลองออนไลน์!
อันดับแรกเราหานายก\$p\$ซึ่ง\$n=p^q\$โดยการเพิ่ม\$p\$จนกว่าเราจะได้ตัวหารบน\$n\$. หลังจากนั้นเราจะพบเลขชี้กำลัง\$q\$ด้วยเคล็ดลับทางคณิตศาสตร์ที่ Sp3000 ค้นพบเป็นครั้งแรกและใช้ในลอการิทึมกำลังที่สมบูรณ์แบบใน Anarchy Golf
เราทราบว่า $$ \frac{n-1}{p-1} = \frac{p^q-1}{p-1} = 1 + p + p^2 \dots+p^{q-2}+p^{q-1}$$โมดูโลทำงาน\$p-1\$เรามี\$p \equiv 1\$ดังนั้นแต่ละ\$q\$ summands ทางด้านขวามือเท่ากับ 1 ดังนั้น: $$ \frac{n-1}{p-1} \equiv q \space \bmod (p-1)$$
ตอนนี้เราต้องการแยก\$q\$. เราต้องการไปที่นั่นโดยใช้ตัวดำเนินการโมดูลัส%(p-1)ทางด้านซ้ายมือ แต่ตอนนี้ต้องว่า\$q<p-1\$ซึ่งไม่รับประกันหรือเราจะได้รับมูลค่าที่แตกต่างออกq%(p-1)ไป
โชคดีที่เราสามารถแก้ไขปัญหานี้ได้ด้วยเคล็ดลับอีกอย่างหนึ่ง เราสามารถแทนที่\$n\$ด้วย\$n^c\$และ\$p\$ด้วย\$p^c\$สำหรับจำนวนบวก\$c\$และยังมี\$n^c=(p^c)^q\$. ตั้งแต่เลขชี้กำลัง\$q\$ที่เกี่ยวข้องจะไม่เปลี่ยนแปลงเราสามารถดึงข้อมูลดังกล่าวข้างต้นได้ แต่ทำให้เป็นเช่นนั้น\$q<p^c-1\$. สำหรับสิ่งนี้\$c=n\$ มากกว่าพอเพียงและสั้นสำหรับการเล่นกอล์ฟแม้ว่าจะทำให้กรณีทดสอบใหญ่หมดเวลา
Bash + Linux utils, 17
factor|dc -e?zr^p
factorใช้ตัวเลขเป็นอินพุตและแยกตัวประกอบ ผลลัพธ์คือหมายเลขอินพุตตามด้วยเครื่องหมายจุดคู่ตามด้วยรายการที่คั่นด้วยระยะห่างของปัจจัยหลักทั้งหมด- รายการนี้ถูกไพพ์
dcซึ่งประเมินค่าeนิพจน์ต่อไปนี้:?อ่านทั้งบรรทัดเป็นอินพุต dc ไม่สามารถแยกวิเคราะห์หมายเลขอินพุตตามด้วยเครื่องหมายจุดคู่ดังนั้นจึงไม่สนใจ จากนั้นจะแยกวิเคราะห์ปัจจัยเฉพาะที่แยกออกจากพื้นที่ทั้งหมดและผลักดันไปยังสแต็กzรับจำนวนรายการบนสแต็ก (จำนวนปัจจัยเฉพาะ) และผลักดันสิ่งนั้นไปยังสแต็กrกลับรายการสองรายการบนสุดในสแตก^เลขชี้กำลังให้คำตอบที่ต้องการpพิมพ์มัน
ลองออนไลน์!
MATL , 8 5 ไบต์
-3 ไบต์ขอบคุณ @LuisMendo
&YFw^
ลองออนไลน์!
J , 9 8 ไบต์
2^~/@p:]
ลองออนไลน์!
2 p: ]ส่งคืนรายการไพรม์และเลขชี้กำลัง^~/@จากนั้นสลับอาร์กิวเมนต์และยกกำลัง
Python 2 , 62 ไบต์
n=input()
p=2
q=-1
while n%p:p+=1
while n:n/=p;q+=1
print q**p
ลองออนไลน์!
C (gcc) -lm 47 ไบต์
p;f(n){for(p=1;n%++p;);p=pow(log(n)/log(p),p);}
ลองออนไลน์!
Brachylog 6 ไบต์
ḋ⟨l^h⟩
ลองออนไลน์! ในการสลายตัวที่สำคัญḋ(ชอบ[5, 5]), ความยาวองค์ประกอบแรกl ^h
โซลูชัน Brachylog-y ที่ดีกว่าและมากกว่าซึ่งยาวกว่าหนึ่งไบต์:
~^ṗᵐ↔≜^
ลองออนไลน์! ย้อนกลับ~^จะได้รับสองหมายเลข[A,B]เพื่อให้ในขณะที่ทั้งสองมีความสำคัญInput = A^B ṗᵐพลิก↔รายการเพื่อ[B,A]ค้นหาตัวเลข≜และผลลัพธ์B^Aจริงๆ
Japt , 6 ไบต์
k
ÊpUg
ลองมัน
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 ไบต์
log(n<-scan(),p<-(b=2:n)[!n%%b][1])^p
ลองออนไลน์!
ความพยายามอย่างดีที่สุดของฉันน่าเศร้าที่ยาวกว่าคำตอบ R ที่ฉลาดมากของซีอาน 1 ไบต์แต่โพสต์ด้วยจิตวิญญาณแห่งการแข่งขัน
ใช้วิธีที่ตรงไปตรงมาในการค้นหาตัวประกอบเฉพาะ ( p<-(b=2:n)[!n%%b][1]) จากนั้นจึงยกกำลัง ( log(n,p)) และสุดท้ายยกเลขชี้กำลังเป็นกำลังของตัวประกอบ ( log(n,p)^p)
R 36 28 1 36 ไบต์
การใช้ความจริงที่ว่าpพลังของnเป็นปัจจัยของn^p:
sum(a<-!max(b<-2:scan())%%b)^b[a][1]
ลองออนไลน์!
แต่การใช้นิยามฟังก์ชันทำได้ดีกว่า (โดยย้ายfunction(m)ไปที่ส่วนหัว!)
f=function(m)
sum(a<-!m%%(b<-2:m))^b[a][1]
ลองออนไลน์!
ด้วยการปรับปรุงความยาวขั้นสูงสุด (1 ไบต์!) โดยกำหนดทุกอย่างเป็นอาร์กิวเมนต์ของฟังก์ชัน (ในส่วนหัวของ Try It Online)
f=function(m,b=2:m,a=!m%%b,d=sum(a)^b[a][1]) d
แต่สิ่งนี้ไม่สอดคล้องกับจิตวิญญาณกอล์ฟรหัส!
Haskell , 42 , 39 ไบต์
f x|r<-[2..x]=[z^w|z<-r,w<-r,w^z==x]!!0
ลองออนไลน์!
- บันทึก 3 ไบต์โดย @xnor
ทับทิม 56 ไบต์
n=gets.to_i
p=2
p+=1while n%p>0
w=p**n-1
p (n**n/w%w)**p
พอร์ตของคำตอบ Python 3 ของ xnor
ลองออนไลน์! (ส่วนหัวและส่วนท้ายได้รับความอนุเคราะห์จาก ovs: D)
ภาษา Wolfram (Mathematica) , 24 ไบต์
#2^#&@@@FactorInteger@#&
ลองออนไลน์!
ส่งคืน{q^p}รายการซิงเกิลตัน
FactorInteger@# (* {{p,q}} *)
#2^#&@@@ (* { q^p } *)
Retina , 59 ไบต์
.+
*
~`(?=(__+?)\1*$)((?=(_+)(\3+)$)\4)+
_+¶$$.($.1*$($#2$*
ลองออนไลน์! ลิงก์มีกรณีทดสอบที่เร็วกว่า คำอธิบาย:
.+
*
แปลงอินพุตเป็นยูนารี
(?=(__+?)\1*$)((?=(_+)(\3+)$)\4)+
pแรกพบปัจจัยขับเคลื่อนที่เล็กที่สุดซึ่งจำเป็นจะต้อง ประการที่สองนับจำนวนครั้งqที่nสามารถแทนที่ได้ด้วยปัจจัยที่เหมาะสมที่สุด (ปัจจัยที่เหมาะสมจะn/pอยู่ที่การส่งครั้งแรกและในที่สุดจะลดลง1ซึ่งไม่ตรงกัน แต่จะไม่ส่งผลต่อผลลัพธ์)
_+¶$$.($.1*$($#2$*
สร้างเวที Retina ซึ่งจะnเป็นข้อมูลและคำนวณ (ในทศนิยม) ผลจากการคูณ1โดยครั้งจึงคำนวณq pq^p
~`
ประเมินโค้ดผลลัพธ์จึงคำนวณผลลัพธ์ที่ต้องการ
Scala , 63 ไบต์
n=>2 to n find(n%_<1)map{p=>import math._;pow(log(n)/log(p),p)}
ลองออนไลน์!
ค้นหาปัจจัยแรกnซึ่งต้องเป็นpเพราะnเป็นอำนาจเฉพาะจากนั้นจะพบ\$\log_p(n)^p\$. ส่งคืนค่าOption[Double]ที่เป็นSome[Double]ถ้าอินพุตถูกต้อง
เยลลี่ 6 ไบต์
ÆFẎṪ*$
ลองออนไลน์!
เยลลี่ 6 ไบต์
ÆFẎ*@Ɲ
ลองออนไลน์!
เยลลี่ 6 ไบต์
ÆfL*ḢƊ
ลองออนไลน์!
5 byter รู้สึกเป็นไปได้ ...
J , 8 ไบต์
2^~/@p:]
ลองออนไลน์!
J มีในตัวที่ให้การแยกตัวประกอบเฉพาะของจำนวนเต็มที่กำหนดในรูปแบบเอกซ์โพเนนต์ จากนั้นก็เป็นเพียงเรื่องของการใช้เลขชี้กำลังในการย้อนกลับ ( ^~) ระหว่างตัวเลขสองตัว
(เกิดขึ้นเหมือนกับคำตอบของโยนาห์แต่อย่างใดไม่ได้สังเกตก่อนที่ฉันจะส่งคำตอบ ... )
เนื่องจากสามารถแก้ไขได้โดยใช้f&.g("Under"; do action g, do action f, then undo action g) นี่คือสิ่งที่น่าสนใจ:
10 ไบต์
|.&.(2&p:)
2&p: Prime factorization into prime-exponent form
|. Swap the prime and exponent
&. Undo `2&p:`; evaluate the "prime" raised to "exponent"
ลองออนไลน์!
10 ไบต์
({.##)&.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"
ลองออนไลน์!
JavaScript (ES7), 47 46 44 ไบต์
ใช้ฟังก์ชันแบบวนซ้ำซึ่งก่อนอื่นค้นหาตัวหารที่เล็กที่สุด\$k\ge2\$ของ\$n\$แล้วนับกี่ครั้ง\$n\$สามารถหารด้วย\$k\$. ผลลัพธ์จะถูกยกขึ้นเป็นพลังของ\$k\$.
n=>(k=2,g=_=>n%k?n>1&&g(k++):1+g(n/=k))()**k
ลองออนไลน์!
แสดงความคิดเห็น
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
อลิซ 13 ไบต์
/ \f~#oE/
i@
ลองออนไลน์!
คำอธิบาย:
/ 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 ไบต์
: 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** ;
ลองออนไลน์!
ทำงานเหมือนNoodle9 คำตอบของ รับจำนวนเต็มและส่งกลับตัวเลขทศนิยมบนสแต็ก FP
มันทำงานอย่างไร
: 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 ไบต์
-1 ไบต์ขอบคุณ @FryAmTheEggman
^lPQhP
ลองออนไลน์!
คำอธิบาย
^lPQhP
l # length of
PQ # prime factors of input
^ # raised to power of
hP # first element in prime factors of input
Io , 57 55 ไบต์
แก้ไขข้อผิดพลาดกรุณาชี้โดย @DominicvanEssen
method(i,p :=2;while(i%p>0,p=p+1);i log(p)floor pow(p))
ลองออนไลน์!
APL (NARS2000 0.5.14)
9 อักขระ
8 ตัว (ขอบคุณผู้เชี่ยวชาญใน APL Orchard):
(⍴*1∘↑)π
มันทำงานอย่างไร:
ใช้อินพุต 8 เป็นตัวอย่าง πแบ่ง 8 ออกเป็นเวกเตอร์ของปัจจัย2 2 2เฉพาะ ส้อม ⍴*1∘↑ใช้เวลาองค์ประกอบหนึ่งจาก2 2 2เป็นตัวแทนนำไปใช้นี้ความยาวของเวกเตอร์2 2 2ซึ่งเป็นให้33^2 = 9
Desmos , 61 10 + 38 = 48 ไบต์
l=log_m(n)
\sum_{m=2}^{n-1}(sign(l-ceil(l))+1)l^m
ดูออนไลน์ (โปรดทราบว่าค่าขนาดใหญ่อาจล้มเหลวเนื่องจาก Desmos จัดการตัวเลขจำนวนมากได้ไม่ดี)
ฉันตัดสินใจกลับมาดูเรื่องนี้อีกครั้งเพราะฉันรู้สึกเหมือนเก่งกว่าตัวเองและฉันจำได้ว่าสิ่งนี้มีความไร้ประสิทธิภาพ ฉันสามารถพบการปรับปรุงเพียงอย่างเดียว แต่ดูเหมือนว่าจะมีมากพอสำหรับการแก้ไข
อินพุตผ่านตัวแปรnเอาต์พุตผ่านการคำนวณครั้งที่สอง หากการป้อนข้อมูลผ่านตัวแปรรู้สึกผิดโปรดเพิ่มสองไบต์สำหรับไฟล์n=.
ไม่ได้ตีกอล์ฟอย่างมีประสิทธิภาพอย่างน่ากลัว ประมาณ 70% ของรหัสนั้นทุ่มเทให้กับการค้นหาปัจจัยเดียวและแน่นอนว่ามีวิธีที่มีประสิทธิภาพมากกว่าในการแยกตัวประกอบตัวเลขใน Desmos แต่ฉันยังไม่พบรหัสนี้และ Desmos ขาดในตัวที่เกี่ยวข้องกับการแยกตัวประกอบหรือจำนวนเฉพาะ .
แต่เราสังเกตว่าตั้งแต่\$p\$และ\$q\$เป็นไพรม์แล้ว\$p*p...*p\$ต้องเป็นเพียงการแยกตัวประกอบของ\$n\$ซึ่งสามารถแสดงด้วยค่าจำนวนเต็มเนื่องจากรายการของ\$p\$s ไม่สามารถแบ่งออกเป็นกลุ่มอื่น ๆ ได้ ดังนั้นเราสามารถโต้ตอบผ่านจำนวนเต็มทั้งหมด\$m \in 2,3,...,n-1\$และหาค่าที่น่าพอใจ\$log_mn \in \mathbb{Z}\$(เซตของจำนวนเต็ม) เราทำสิ่งนี้ในรหัสโดยใช้sign(log_m(n)-ceil(log_m(n)))+1ซึ่งให้ 1 ที่ดีแก่เราเมื่อจำนวนเต็มและ 0 เมื่อไม่ เราคูณด้วยlog_m(n)^mเพื่อให้ค่าใหม่ของเราและรวมผลลัพธ์สำหรับค่าทั้งหมด 2 ถึง n-1 เพื่อแยกคำตอบออกมา
แกลบ 5 ไบต์
§^←Lp
ลองออนไลน์!