পাইথনে প্রাইমোরিয়াল প্রাইম চেক করুন

मान लीजिए हमारे पास एक संख्या n है, हमें जांचना है कि क्या n एक प्राइमोरियल प्राइम है या नहीं। एक संख्या को प्राइमोरियल प्राइम कहा जाता है जब यह pN# + 1 या pN# - 1 के रूप में एक अभाज्य संख्या होती है, जहां pN# पहले N अभाज्य संख्याओं के गुणनफल को दर्शाता है।

यदि इनपुट 29 जैसा है, तो आउटपुट True होगा क्योंकि 29, N=3 के लिए pN - 1 के रूप में प्राइमोरियल प्राइम है, प्राइमोरियल 2*3*5 = 30 और 30-1 = 29।

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

MAX := 100000
prime := आकार MAX की एक सूची, True से भरी हुई
arr := एक नई सूची
SieveOfEratosthenes() नामक एक फंक्शन परिभाषित करें।
- pri को 2 से int(sqrt(MAX)) + 1 तक के लिए, करें:
  - यदि prime[pri] True है, तो
    - i को pri*2 से MAX तक pri बढ़ाकर, करें: prime[i] := False
- pri को 2 से MAX तक के लिए, करें:
  - यदि prime[pri] शून्येतर है, तो pri को arr के अंत में जोड़ें
मुख्य मेथड से, निम्नलिखित करें:
- यदि prime[n] शून्य है, तो False लौटाएं
- product := 1, i := 0
- जब तक product < n, करें:
  - product := product * arr[i]
  - यदि product + 1 == n या product - 1 == n, तो True लौटाएं
  - i := i + 1
- False लौटाएं

उदाहरण

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

from math import sqrt
MAX = 100000
prime = [True] * MAX
arr = []
def SieveOfEratosthenes():
    for pri in range(2, int(sqrt(MAX)) + 1):
        if prime[pri] == True:
            for i in range(pri * 2, MAX, pri):
                prime[i] = False
    for pri in range(2, MAX):
        if prime[pri]:
            arr.append(pri)

def check_primorial_prime(n):
    if not prime[n]:
        return False
    product, i = 1, 0
    while product < n:
        product *= arr[i]
        if product + 1 == n or product - 1 == n:
            return True
        i += 1
    return False

SieveOfEratosthenes()
n = 29
print(check_primorial_prime(n))

इनपुट

आउटपुट

True