ตรวจสอบว่าตัวเลขที่กำหนดเป็น Euclid Number หรือไม่ใน Python

สมมติว่าเรามีตัวเลข n เราต้องตรวจสอบว่า n เป็นเลขยูคลิดหรือไม่ อย่างที่เราทราบกันดีว่าเลขยุคลิดเป็นจำนวนเต็มซึ่งสามารถแสดงเป็น

n=P_n +1

โดยที่ผลคูณของจำนวนเฉพาะ n ตัวแรกอยู่ที่ไหน

ดังนั้นหากอินพุตเป็น n =211 ผลลัพธ์จะเป็น True n สามารถแสดงเป็น

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

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

• MAX :=10000
• primes :=รายการใหม่
• กำหนดฟังก์ชัน generate_all_primes() นี่จะใช้เวลา
• prime :=รายการขนาด MAX และเติม True
• x :=2
• ในขณะที่ x * x
• ถ้าไพรม์[x] เป็นจริง ดังนั้น
  • สำหรับ i ในช่วง x * 2 ถึง MAX ให้อัปเดตในแต่ละขั้นตอนทีละ x ทำ
    • prime[i] :=เท็จ
  • x :=x + 1

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

โค้ดตัวอย่าง

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

อินพุต

211

ผลลัพธ์

True