पायथन का उपयोग करके n का kवां गुणनखंड खोजने का प्रोग्राम

मान लीजिए हमारे पास दो सकारात्मक मान n और k हैं। अब n के सभी गुणनखंडों की सूची पर विचार करें जो आरोही क्रम में सॉर्ट की गई है, हमें इस सूची में kवां गुणनखंड ढूंढना है। यदि k से कम गुणनखंड हैं, तो -1 वापस करें।

उदाहरण के लिए, यदि इनपुट n = 28 k = 4 है, तो आउटपुट 7 होगा क्योंकि, 28 के गुणनखंड [1,2,4,7,14,28] हैं, चौथा 7 है।

हल करने के चरण

• यदि k, 1 के समान है, तो

  • 1 वापस करें

• cand := एक तत्व [1] वाली सूची

• i को 2 से 1 + floor(sqrt(n)) तक की रेंज में लिए करें

  • यदि n mod i, 0 के समान है, तो

    • i को cand के अंत में डालें

• m := cand का आकार

• यदि k > 2*m या (k, 2*m के समान है और n, cand के अंतिम तत्व का वर्ग है)

  • -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