[SOLUTION] Guess the winner! SOLUTION CODECHEF

Problem SOLUTION CODECHEF

Alice and Bob play a game.

They start with the integer $N$ and take turns, with Alice going first.
On their turn, a player must select an odd prime factor $p$ of $N$, and subtract it from $N$ (so $N$ changes to $N-p$).

The player who cannot make a move loses (that is, if either $N=0$ or $N$ has no odd prime factors).
If Alice and Bob play optimally, who wins the game?

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• The only line of each test case contains a single integer $N$ — the value Alice and Bob start with.

Output Format

For each test case, output on a new line the winner of the game — either "Alice" or "Bob" (without quotes).

Each letter of the output may be printed in either uppercase or lowercase, i.e, the strings Bob, BOB, bOb, and boB will all be treated as equivalent.

Constraints

Sample 1:

2
2
5

Bob
Alice

Explanation:

Test case $1$: $2$ does not have any odd prime factor, so Alice cannot make a move and will lose immediately.

Test case $2$: $N=5$. Alice can choose $p=5$, an odd prime factor of $N$, and subtract it.
This makes $N=0$, and Bob cannot move; making Alice the winner.

 SOLUTION

import math

def is_prime(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True

def find_odd_prime_factors(n):
factors = []
if n % 2 == 0:
while n % 2 == 0:
n //= 2
factors.append(2)
for i in range(3, int(math.sqrt(n)) + 1, 2):
if is_prime(i):
while n % i == 0:
n //= i
factors.append(i)
if n > 1:
factors.append(n)
return factors

def game_winner(N):
odd_prime_factors = find_odd_prime_factors(N)
if len(odd_prime_factors) % 2 == 0:
return “Bob”
else:
return “Alice”

# Input
T = int(input())
for _ in range(T):
N = int(input())
winner = game_winner(N)
print(winner)