在Python中查找一组元素删除游戏的获胜者

假设我们有一个第一个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
筛子：一个大小为100000的数组，最初所有都是0
对于2到99999的i，做以下操作
- 如果筛子[i]与0相同，则
  - primes[i]：=primes[i-1]+1
  - 对于从i到100000的每个步骤更新，更新为i
  - 筛子[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))