ตรวจสอบ Primorial Prime ใน Python

ภาพรวม

Primorial Prime คือจำนวนเฉพาะที่อยู่ในรูป pₙ# + 1 หรือ pₙ# - 1 โดย pₙ# = ผลคูณของจำนวนเฉพาะ n ตัวแรก (Primorial)

ตัวอย่าง

n = 29

Primorial N=3: 2×3×5 = 30

30 - 1 = 29 → 29 เป็น Primorial Prime (รูป pₙ# - 1) → True

อัลกอริทึม

1. Sieve of Eratosthenes หาจำนวนเฉพาะทั้งหมด ≤ MAX
2. ถ้า n ไม่ใช่จำนวนเฉพาะ → False
3. คูณจำนวนเฉพาะตามลำดับ (product) จน product ≥ n:
   • ถ้า product ± 1 == n → True

โค้ด Python

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))

Primorial Primes ที่รู้จัก

2, 3, 5, 7, 29, 31, 211, 2309, 2311, 30029, 200560490131, ...

ผลลัพธ์

True