โปรแกรมหาตัวประกอบ kth ของ n โดยใช้ Python

สมมติว่าเรามีค่าบวกสองค่า n และ k ตอนนี้ให้พิจารณาว่าเรามีรายชื่อปัจจัยทั้งหมดของ n ที่เรียงลำดับจากน้อยไปหามากแล้ว เราต้องหาตัวประกอบ kth ในรายการนี้ หากมีตัวประกอบน้อยกว่า k ตัว ให้คืนค่า -1

ดังนั้น ถ้าอินพุตเป็นเหมือน n =28 k =4 ผลลัพธ์จะเป็น 7 เพราะตัวประกอบของ 28 คือ [1,2,4,7,14,28] ตัวที่สี่คือ 7

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

• ถ้า k เท่ากับ 1 แล้ว

  • กลับ 1

• cand :=รายการที่มีองค์ประกอบเดียว [1]

• สำหรับฉันอยู่ในช่วง 2 ถึง 1 + ชั้นของ (รากที่สองของ n) ทำ

  • ถ้า n mod i เหมือนกับ 0 แล้ว

    • ใส่ i ต่อท้ายแคน

  • m :=ขนาดของแคน

• ถ้า k> 2*m หรือ (k เท่ากับ 2*m และ n =(องค์ประกอบสุดท้ายของ cand)^2)

  • กลับ -1

• ถ้า k <=m แล้ว

  • ส่งคืนแคน[k-1]

• แฟคเตอร์ :=cand[2*m - k]

• ส่งคืนผลหารของ n/factor

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

ตัวอย่าง

from math import floor
def solve(n ,k):
   if k == 1:
      return 1
   cand = [1]
   for i in range(2, 1+floor(pow(n, 0.5))):
      if n%i == 0:
         cand.append(i)
      m = len(cand)
      if k > 2*m or (k == 2*m and n == cand[-1]**2):
         return -1
      if k <= m:
         return cand[k-1]
      factor = cand[2*m - k]
      return n//factor
n = 28
k = 4
print(solve(n ,k))

อินพุต

28, 4

ผลลัพธ์

7