पायथन में जांचें कि कोई पूर्णांक दो सेमी-प्राइम संख्याओं के योग के रूप में व्यक्त किया जा सकता है या नहीं

मान लीजिए हमारे पास एक संख्या n है, हमें यह जांचना है कि क्या n को दो सेमी-प्राइम संख्याओं के योग के रूप में व्यक्त किया जा सकता है या नहीं।

जैसा कि हम जानते हैं, सेमी-प्राइम वह संख्या होती है जिसे दो अभाज्य संख्याओं के गुणनफल के रूप में व्यक्त किया जा सकता है। पहले कुछ सेमी-प्राइम संख्याएं (1-100 रेंज में): 4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95।

उदाहरण के लिए, यदि इनपुट n = 108 है, तो आउटपुट True होगा क्योंकि यह 14 और 94 का योग है जो दोनों सेमी-प्राइम हैं।

समाधान दृष्टिकोण

हम पहले सभी सेमी-प्राइम संख्याओं को एक निश्चित सीमा (MAX) तक प्रीकंप्यूट करते हैं, फिर जांचते हैं कि क्या n को दो सेमी-प्राइम के योग के रूप में लिखा जा सकता है।

एल्गोरिदम चरण:

1. MAX = 10000 सेट करें (मान लें कि दिए गए इनपुट 1 से 10000 तक के सेमी-प्राइम के योग हैं)
2. nums सूची और s_prime_flags ऐरे बनाएं
3. get_semi_primes() फ़ंक्शन परिभाषित करें जो 2 से MAX-1 तक प्रत्येक संख्या के लिए:
• अभाज्य गुणनखंडों की गिनती करें (अधिकतम 2)
• यदि ठीक 2 अभाज्य गुणनखंड हैं, तो इसे सेमी-प्राइम के रूप में चिह्नित करें
4. मुख्य विधि में get_semi_primes() कॉल करें
5. प्रत्येक सेमी-प्राइम nums[i] के लिए (जब तक nums[i] <= n//2):
• यदि n - nums[i] भी सेमी-प्राइम है, तो True लौटाएं
6. यदि कोई जोड़ी नहीं मिली, तो False लौटाएं

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

MAX = 10000
nums = []
s_prime_flags = [False] * MAX

def get_semi_primes():
    for i in range(2, MAX):
        count = 0
        num = i
        j = 2
        while count < 2 and j * j <= num:
            while num % j == 0:
                num //= j
                count += 1
            j += 1
        if num > 1:
            count += 1
        if count == 2:
            s_prime_flags[i] = True
            nums.append(i)

def solve(n):
    get_semi_primes()
    i = 0
    while nums[i] <= n // 2:
        if s_prime_flags[n - nums[i]]:
            return True
        i += 1
    return False

n = 108
print(solve(n))  # True

इनपुट

108

आउटपुट

True

नोट:

दिए गए उदाहरण में इनपुट [4, 2, 3], 11 दिखाया गया है जो इस समस्या के संदर्भ में असंगत प्रतीत होता है। सही इनपुट एक पूर्णांक n होना चाहिए।