Kiểm tra xem một số có phải là Nguyên tố Nguyên tố hay không trong Python

Giả sử chúng ta có một số n, chúng ta phải kiểm tra xem n có phải là số nguyên tố hay không. Một số được cho là số nguyên tố khi nó là số nguyên tố có dạng pN # + 1 hoặc pN # - 1, trong đó pN # cho biết số nguyên tố của pN sao cho tích của N số nguyên tố đầu tiên.

Vì vậy, nếu đầu vào là 29, thì đầu ra sẽ là Đúng vì 29 là Nguyên tố nguyên tố có dạng pN - 1 nếu N =3, Nguyên tố là 2 * 3 * 5 =30 và 30-1 =29.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• MAX:=100000
• prime:=Một danh sách có kích thước MAX và điền bằng True
• arr:=một danh sách mới
• Xác định một hàm SieveOfEratosthenes (). Điều này sẽ mất
• đối với số pri trong phạm vi 2 đến int (căn bậc hai của (MAX)) + 1, hãy thực hiện
  • nếu số nguyên tố [pri] giống với True, thì
    • đối với tôi trong phạm vi pri * 2 đến MAX, cập nhật từng bước một, thực hiện
      • prime [i]:=False
• đối với giá trị pri trong phạm vi 2 đến MAX, thực hiện
  • nếu số nguyên tố [pri] khác 0, thì
    • chèn pri vào cuối arr
• Từ phương pháp chính, hãy thực hiện như sau -
• nếu số nguyên tố [n] bằng 0, thì
  • trả về Sai
• sản phẩm:=1, i:=0
• while product
• product:=product * arr [i]
• nếu product + 1 giống n hoặc product - 1 giống n, thì
  • trả về True
• i:=i + 1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

29

Đầu ra

True