पायथन में प्राइमोरियल प्राइम की जांच

समस्या विवरण

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

उदाहरण

इनपुट: 29

आउटपुट: True

व्याख्या: N=3 के लिए, प्राइमोरियल = 2×3×5 = 30, 30-1 = 29 (अभाज्य)

एल्गोरिदम

1. सिव ऑफ एराटोस्थनीज से अभाज्य संख्याएं जनरेट करें (MAX=100000 तक)
2. यदि n अभाज्य नहीं: False
3. product = 1, अभाज्य संख्याओं को क्रम से गुणा करें:
   • यदि product + 1 == n या product - 1 == n: True
   • यदि product >= n: ब्रेक
4. False

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

from math import sqrt

MAX = 100000
prime = [True] * MAX
primes = []

def SieveOfEratosthenes():
    for p in range(2, int(sqrt(MAX)) + 1):
        if prime[p]:
            for i in range(p*2, MAX, p):
                prime[i] = False
    for p in range(2, MAX):
        if prime[p]:
            primes.append(p)

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

SieveOfEratosthenes()
print(check_primorial_prime(29))

इनपुट

29

आउटपुट

True