পাইথনে n-এর k-তম ফ্যাক্টর বের করার প্রোগ্রাম

দুটি ধনাত্মক মান n এবং k দেওয়া আছে। n-এর সব ফ্যাক্টরগুলো আরোহী ক্রমে সাজানো হলে k-তম ফ্যাক্টরটি বের করতে হবে। যদি মোট ফ্যাক্টর k-এর চেয়ে কম হয়, তবে -1 ফেরত দিন।

যেমন, n = 28, k = 4 হলে আউটপুট ৭। কারণ ২৮-এর ফ্যাক্টরগুলো: [1,2,4,7,14,28], চতুর্থটি ৭।

সমাধানের ধাপসমূহ

যদি k == 1 হয়, তবে ১ ফেরত দিন।
cand := [1] (প্রাথমিক ফ্যাক্টর লিস্ট)
i = 2 থেকে floor(sqrt(n)) পর্যন্ত লুপ:

যদি n % i == 0 হয়, তবে cand-এ i যোগ করুন।

m := 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