जांचें कि क्या एक पूर्णांक को पायथन में दो अर्ध-अभाज्य संख्याओं के योग के रूप में व्यक्त किया जा सकता है

मान लीजिए कि हमारे पास एक संख्या 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 जैसा है, तो आउटपुट ट्रू होगा क्योंकि यह 14 का योग है और 94 दोनों सेमी-प्राइम हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

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

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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]] == True:
         return True
      i += 1
   return False
n = 108
print(solve(n))

इनपुट

[4, 2, 3], 11

आउटपुट

True