ตรวจสอบว่าเลขเป็น Euclid Number หรือไม่ด้วย Python

Euclid Number: จำนวนเต็มรูปแบบ P_n + 1 โดย P_n = ผลคูณของ Prime แรก n ตัว

ตัวอย่าง

n = 211 → True เพราะ 211 = (2×3×5×7) + 1

อัลกอริทึม

1. Sieve of Eratosthenes หา Prime ทั้งหมดจน MAX
2. คูณ Prime ตัวแรก们 เรียงลำดับ (mul = 1, mul *= prime[i])
3. ทุกขั้นตอนตรวจสอบ mul + 1 == n
4. ถ้า mul ≥ n หยุด → False

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

MAX = 10000
primes = []

def generate_all_primes():
    prime = [True] * MAX
    x = 2
    while x * x < MAX:
        if prime[x]:
            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))

Input / Output

Input: 211
Output: True