Kiểm tra xem số đã cho có phải là Số Euclid 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ố Euclid hay không. Như chúng ta biết số Euclid là số nguyên có thể được biểu diễn dưới dạng

n =P _n +1

tích của n số nguyên tố đầu tiên ở đâu.

Vì vậy, nếu đầu vào là n =211, thì đầu ra sẽ là True n có thể được biểu diễn là

211 =(2 × 3 × 5 × 7) +1

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

• MAX:=10000
• số nguyên tố:=một danh sách mới
• Xác định một hàm create_all_primes (). Điều này sẽ mất
• prime:=một danh sách có kích thước MAX và điền bằng True
• x:=2
• trong khi x * x
• nếu số nguyên tố [x] là True, thì
  • đối với tôi trong phạm vi x * 2 đến MAX, cập nhật từng bước x, thực hiện
    • prime [i]:=False
  • x:=x + 1

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

Mã mẫu

MAX = 10000
primes = []
 
def generate_all_primes():
   prime = [True] * MAX
 
   x = 2
   while x * x < MAX :
      if prime[x] == True:
         for i in range(x * 2, MAX, x):
           prime[i] = False
      x += 1

   for x in range(2, MAX):
      if prime[x]:
         primes.append(x)

def solve(n):
   generate_all_primes()
   mul = 1
   i = 0
 
   while mul < n :
      mul = mul * primes[i]
      if mul + 1 == n:
         return True
      i += 1
   return False

n = 211
print(solve(n))

Đầu vào

211

Đầu ra

True