पायथन में ट्रोजन नंबर की जांच

समस्या विवरण

एक संख्या n दी गई है, जांचें कि क्या यह ट्रोजन नंबर है। ट्रोजन नंबर = मजबूत संख्या (हर अभाज्य गुणक कम से कम दो बार आता है) लेकिन पूर्ण घात नहीं।

उदाहरण

इनपुट: 72

आउटपुट: True

72 = 2³ × 3² — सभी अभाज्य गुणक ≥2 बार, लेकिन 72 = a^b रूप में नहीं।

एल्गोरिदम

1. check_perfect_pow(n): जांचें कि क्या n = x^y (y≥2)
2. check_strong_num(n): अभाज्य गुणनखंड करके प्रत्येक की आवृत्ति ≥2 जांचें
3. ट्रोजन यदि: not perfect_pow and strong_num

पायथन कार्यान्वयन

from math import sqrt

def check_perfect_pow(n):
    if n == 1:
        return True
    for x in range(2, int(sqrt(n)) + 1):
        y = 2
        p = x ** y
        while p <= n and p > 0:
            if p == n:
                return True
            y += 1
            p = x ** y
    return False

def check_strong_num(n):
    count = {}
    temp = n
    while temp % 2 == 0:
        temp //= 2
        count[2] = count.get(2, 0) + 1
    for i in range(3, int(sqrt(temp)) + 1, 2):
        while temp % i == 0:
            temp //= i
            count[i] = count.get(i, 0) + 1
    if temp > 2:
        count[temp] = count.get(temp, 0) + 1
    return all(v >= 2 for v in count.values())

def isTrojan(n):
    return not check_perfect_pow(n) and check_strong_num(n)

print(isTrojan(72))

इनपुट

72

आउटपुट

True