在 Python 中查找集合元素移除游戏获胜者的程序

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

• Amal 总是先玩

• 在每次移动期间，当前玩家从集合中选择一个质数 p。然后玩家从集合中移除 p 和它的所有倍数。

• 谁不动谁输游戏如果我们有n，我们必须找到获胜者的名字。

所以，如果输入像 n = 5，那么输出将是 Amal，因为初始集合是 {1,2,3,4,5}。现在让 Amal 选择一个数 p = 2，并从集合中移除 2, 4，所以当前集合为 {1,3,5}，还剩下两个素数，所以 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))

输入

5

Amal