สมมติว่าเรามีจำนวนเต็มบวก n และ k พิจารณารายการตัวประกอบของ n เรียงจากน้อยไปมาก เราต้องหาตัวประกอบตัวที่ k ถ้ามีน้อยกว่า k ตัวให้คืน -1
เช่น ถ้าข้อมูลเข้าเป็น n = 28 k = 4 ผลลัพธ์จะเป็น 7 เพราะตัวประกอบของ 28 คือ [1,2,4,7,14,28] ตัวที่ 4 คือ 7
ขั้นตอนการแก้ปัญหา
- ถ้า k == 1: คืน 1
- สร้างลิสต์ cand = [1] เก็บตัวประกอบเล็ก (≤ √n)
- วนลูป i จาก 2 ถึง floor(√n):
- ถ้า n % i == 0: เพิ่ม i เข้า cand
- m = len(cand)
- ถ้า k > 2*m หรือ (k == 2*m และ n == cand[-1]²): คืน -1 (ตัวประกอบไม่พอ)
- ถ้า k ≤ m: คืน cand[k-1] (อยู่ในครึ่งล่าง)
- มิฉะนั้น: factor = 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
