ตรวจสอบว่าตัวเลขเป็น Primorial Prime หรือไม่ใน Python

สมมติว่าเรามีจำนวน n เราต้องตรวจสอบว่า n เป็นจำนวนเฉพาะไพรมอเรียลหรือไม่ กล่าวได้ว่าจำนวนเฉพาะไพรมอเรียลเมื่อเป็นจำนวนเฉพาะของรูปแบบ pN# + 1 หรือ pN# – 1 โดยที่ pN# บ่งชี้ถึงไพรมอเรียลของ pN ส่งผลให้ผลคูณของจำนวนเฉพาะ N ตัวแรก

ดังนั้น หากอินพุตเท่ากับ 29 เอาต์พุตจะเป็น True เนื่องจาก 29 คือ Primorial Prime ของรูปแบบ pN - 1 หาก N=3, Primorial คือ 2*3*5 =30 และ 30-1 =29

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

MAX :=100000
prime :=รายการขนาด MAX และเติม True
arr :=รายการใหม่
กำหนดฟังก์ชัน SieveOfEratosthenes() นี่จะใช้เวลา
สำหรับ pri ในช่วง 2 ถึง int(สแควร์รูทของ (MAX)) + 1 ทำ
- ถ้าไพรม์[pri] เหมือนกับ True แล้ว
  - สำหรับ i ในช่วง pri * 2 ถึง MAX ให้อัปเดตในแต่ละขั้นตอนโดย pri ทำ
    - prime[i] :=เท็จ
สำหรับ pri ในช่วง 2 ถึง MAX ให้ทำ
- ถ้าไพรม์[pri] ไม่ใช่ศูนย์ ดังนั้น
  - ใส่ pri ต่อท้าย arr
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
ถ้าไพรม์[n] เป็นศูนย์ ดังนั้น
- คืนค่าเท็จ
สินค้า :=1, ผม :=0
ในขณะที่ผลิตภัณฑ์
ผลิตภัณฑ์ :=ผลิตภัณฑ์ * arr[i]
ถ้า product + 1 เหมือนกับ n หรือ product - 1 เหมือนกับ n แล้ว
- คืนค่า True
ผม :=ผม + 1

คืนค่าเท็จ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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