Kiểm tra số nguyên tố Primorial trong Python

Số Primorial prime là số nguyên tố dạng pN# + 1 hoặc pN# - 1, trong đó pN# là tích của N số nguyên tố đầu tiên.

Ví dụ: 29 là Primorial prime vì 2*3*5 = 30, 30-1 = 29.

Thuật toán

Sàng Eratosthenes tìm số nguyên tố đến MAX
Nếu n không phải nguyên tố → False
Tính tích các số nguyên tố liên tiếp, kiểm tra product ± 1 == n

Ví dụ mã Python

from math import sqrt
MAX = 100000
prime = [True] * MAX
arr = []
def SieveOfEratosthenes():
    for pri in range(2, int(sqrt(MAX)) + 1):
        if prime[pri]:
            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))

Đầu vào

Đầu ra

True