โปรแกรมหาจำนวนวิธีที่เราจะได้ตัวเลขซึ่งเป็นผลรวมของกำลังที่ n ของจำนวนเฉพาะใน Python

สมมติว่าเรามีจำนวน x และอีกจำนวนหนึ่ง n เราต้องหาหลายวิธีที่จะได้ x เป็นผลรวมของยกกำลังที่ n ของจำนวนเฉพาะบางตัว

ดังนั้น ถ้าอินพุตเป็นเหมือน x =100 n =2 ผลลัพธ์จะเป็น 3 เพราะคำตอบที่เป็นไปได้คือ 6^2 + 8^2, 10^2 และ 1^2 + 3^2 + 4^2 + 5^ 2 + 7^2.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ตอบ :=0
• กำหนดวิธีการที่เรียกว่า Solve() ซึ่งจะใช้พารามิเตอร์สี่ตัว x, n, cn และ cs ค่าเริ่มต้น
• ค่าสำหรับ cs =0, cn =1
• p :=cn^n
• ในขณะที่ p + cs
• ans :=ans + แก้ (x, n, cn + 1, p + cs)
• cn :=cn + 1
• p :=cn^n

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

from math import pow

def solve(x, n, cn = 1, cs = 0):
   ans = 0
   p = pow(cn, n)
   while p + cs < x:
      ans += solve(x, n, cn + 1, p + cs)
      cn = cn + 1
      p = pow(cn, n)

   if p + cs == x:
      ans = ans + 1
   return ans

x = 100
n = 2
print(solve(x, n))

อินพุต

100, 2

ผลลัพธ์

3