Xác định người thắng trò chơi loại bỏ số nguyên tố và bội số trong Python

Tập hợp {1..n}. Amal và Bimal lần lượt chọn số nguyên tố p từ tập, loại bỏ p và tất cả bội số của p. Người không chọn được thua. Amal đi trước. Tìm người thắng.

Ví dụ: n=5 → Amal thắng.

Giải thuật

• Số lượng số nguyên tố ≤ n quyết định: nếu số lượng nguyên tố là chẵn → Bimal thắng, lẻ → Amal thắng.
• Sàng Eratosthenes tính trước số nguyên tố đến 100000.

Ví dụ mã Python

primes = [0] * 100001
sieve = [0] * 100001
for i in range(2, 100000):
    if sieve[i] == 0:
        primes[i] = primes[i-1] + 1
        for j in range(i, 100001, i):
            sieve[j] = i
    else:
        primes[i] = primes[i-1]

def solve(n):
    return "Bimal" if primes[n] % 2 == 0 else "Amal"

n = 5
print(solve(n))  # Output: Amal

Đầu vào

5

Đầu ra

Amal