Kiểm tra số có phải Euclid Number trong Python Kiểm tra số có phải Euclid Number trong Python

Euclid number có dạng P_n + 1, trong đó P_n là tích của n số nguyên tố đầu tiên.

Ví dụ: 211 = (2*3*5*7) + 1 → True.

Thuật toán

• Sàng Eratosthenes (MAX=10000) tạo danh sách số nguyên tố primes.
• Nhân dần các số nguyên tố đầu tiên (mul), sau mỗi lần nhân kiểm tra mul+1 == n.
• Nếu khớp → True, nếu mul >= n → dừng, trả về False.

Ví dụ code

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

Đầu vào

211

Đầu ra

True