用 Python 编写程序，找出集合元素移除游戏的赢家

pythonserver side programmingprogramming更新于 2026/1/30 18:20:17

假设我们有一组前 n 个自然数 {1..n}。Amal 和 Bimal 正在玩游戏。游戏规则如下

Amal 总是先出手
在每次移动过程中，当前玩家从集合中选择一个素数 p。然后玩家从集合中移除 p 及其所有倍数。
没有移动的人将输掉游戏。如果有 n，我们必须找出赢家的名字。

因此，如果输入为 n = 5，则输出将是 Amal，因为初始集合为 {1,2,3,4,5}。现在让 Amal 选择一个数字 p = 2，并从集合中删除 2、4，因此当前集合为 {1,3,5}，剩下两个素数，因此 Bimal 可以选择其中任何一个，但没有剩余元素可以删除，最后 Amal 删除另一个素数并赢得游戏。

为了解决这个问题，我们将遵循以下步骤 −

primes := 大小为 100000 的数组，最初所有都是 0
sieve := 大小为 100000 的数组，最初所有都是 0
对于 i 在 2 到 99999 的范围内，执行
- 如果 sieve[i] 与 0 相同，则
  - primes[i] := primes[i-1]+1
  - 对于 j 在 i 到100000，每一步更新 i，执行
    - sieve[j] := i
- 否则，
  - primes[i] := primes[i-1]
从主方法执行以下操作 −
如果 primes[n] 为奇数，则返回 "Bimal"，否则返回 "Amal"

示例

让我们看看下面的实现以便更好地理解 −

primes = [0 for i in range(100001)]
sieve = [0 for i in range(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))