Problem Statement :

Alice and Bob invented the following silly game:

The game starts with an integer, , that's used to build a  of  distinct integers in the inclusive range from  to  (i.e., ).
Alice always plays first, and the two players move in alternating turns.
During each move, the current player chooses a prime number, , from . The player then removes  and all of its multiples from .
The first player to be unable to make a move loses the game.
Alice and Bob play  games. Given the value of  for each game, print the name of the game's winner on a new line. If Alice wins, print Alice; otherwise, print Bob.

Note: Each player always plays optimally, meaning they will not make a move that causes them to lose the game if some better, winning move exists.

Input Format

The first line contains an integer, , denoting the number of games Alice and Bob play.
Each line  of the  subsequent lines contains a single integer, , describing a game.

Output Format

For each game, print the name of the winner on a new line. If Alice wins, print Alice; otherwise, print Bob.

Solution :

In  C  :

#include <stdio.h>

int main(void) {

int t;scanf("%d",&t);
while(t--)
{
int i,j;
int n;scanf("%d",&n);
int arr;
for(i=1;i<=100000;i++)
arr[i]=1;

for(i=2;i<=100000;i++)
{
if(arr[i]==1)
{
for(j=2*i;j<=100000;j+=i)
arr[j]=0;
}
}
arr=0;
int c=0;
for(i=1;i<=n;i++)
if(arr[i]==1)
c++;
if(c%2==0)
printf("Bob\n");
else
printf("Alice\n");
}

return 0;
}

In  C++ :

#include <bits/stdc++.h>

using namespace std;

int N;
int pr;

int main()
{
scanf("%d", &N);
for(int i=2; i<=100000; i++)
pr[i]=1;
for(int i=2; i<=100000; i++) if(pr[i])
for(int j=i*2; j<=100000; j+=i)
pr[j]=0;
for(int i=3; i<=100000; i++)
pr[i]^=pr[i-1];
while(N--)
{
int x;
scanf("%d", &x);
if(pr[x])
printf("Alice\n");
else
printf("Bob\n");
}
return 0;
}

In  Java :

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<Integer> primes = new ArrayList<Integer>();
for (int i = 3; i <= 100000; i+=2) {
int sqrt = (int)Math.sqrt(i);
boolean prime = true;
for (int p : primes) {
if (p > sqrt)
break;
if (i%p==0) {
prime = false;
break;
}
}
if (prime)
}
int[] counts = new int;
int currIndex = 0;
for (int i = 0; i <= 100000; i++) {
if (currIndex < primes.size() && primes.get(currIndex) == i)
currIndex++;
counts[i] = currIndex;
}
int g = sc.nextInt();
for (int i = 0; i < g; i++) {
System.out.println(counts[sc.nextInt()]%2==0?"Bob":"Alice");
}
}
}

In  Python3 :

#!/bin/python3

import sys

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

g = int(input().strip())
for a0 in range(g):
n = int(input().strip())