# Prime Game Solution CodeChef

Page Contents

## Prime Game Solution February Challenge 2021

Chef and Divyam are playing a game with the following rules:

• First, an integer X!X! is written on a board.
• Chef and Divyam alternate turns; Chef plays first.
• In each move, the current player should choose a positive integer DD which is divisible by up to YY distinct primes and does not exceed the integer currently written on the board. Note that 11 is not a prime.
• DD is then subtracted from the integer on the board, i.e. if the integer written on the board before this move was AA, it is erased and replaced by A−DA−D.
• When one player writes 00 on the board, the game ends and this player wins.

Given XX and YY, determine the winner of the game.

Also See: February Long Challenge 2021 Solutions

### Input

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first and only line of each test case contains two space-separated integers XX and YY.

### Output

For each test case, print a single line containing the string `"Chef"` if Chef wins the game or `"Divyam"` if Divyam wins (without quotes).

### Constraints

• 1≤T≤1061≤T≤106
• 1≤X,Y≤1061≤X,Y≤106

• 1≤T≤1021≤T≤102
• 1≤X≤61≤X≤6

Subtask #3 (85 points): original constraints

```3
1 2
3 1
2021 42
```

```Chef
Divyam
Divyam
```

### Explanation

Example case 1: Since D=1D=1 is divisible by 00 primes, Chef will write 00 and win the game in the first move.

Example case 2: Chef must choose DD between 11 and 55 inclusive, since D=6D=6 is divisible by more than one prime. Then, Divyam can always choose 6−D6−D, write 00 on the board and win the game.

## Solution

Program C:

```#include <stdio.h>
#include<string.h>
#include<math.h>
#define vmp_2000080124
long int preetamCheck(long int qwerty) {
if(qwerty<=1)
{
return 0;
}
if(qwerty != 2 && qwerty != 3) {

for(long int mp = 2; mp <= sqrt(qwerty); mp++) {

if (qwerty % mp == 0) {

return 0;
}
}
return 1;
}
else {

return 1;
}
}
int main()
{
long int ti_m;
scanf("%ld",&ti_m);
long int preetamNum;
long int countPreetam;

}

while(ti_m--){

long int xVal, yVal;
scanf("%ld %ld", &xVal, &yVal);

if(countPreetam[xVal] > yVal)
printf("Divyam\n");
else
printf("Chef\n");
for(int i=0;i<98;i++);
}
return 0;
}```

Program C++:

```#include <bits/stdc++.h>
using namespace std;

vector<int>prefix(1000001);
bool prime;

int main()
{
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= 1000001; p++) {
if (prime[p] == true) {
for (int i = p * 2; i <= 1000001; i += p)
prime[i] = false;
}
}
prefix = 0;
prefix = 0;
for (int p = 2; p <= 1000001; p++) {
prefix[p] = prefix[p - 1];
if (prime[p])
prefix[p]++;
}

int n, X, Y, ans;
cin >> n;
for(int i = 0; i < n; i++){
scanf("%d%d", &X, &Y);
if(prefix[X]>Y){
printf("Divyam\n");
}
else{
printf("Chef\n");
}
}

return 0;
}```

Program Java:

```import java.io.*;
import java.lang.*;
import java.util.*;
class GFG {
public static int[] array = new int;

public static void  primeGame(int num)
{

boolean pri[] = new boolean[num + 1];
for (int i = 0; i <= num; i++)
pri[i] = true;

for (int p = 2; p * p <= num; p++)
{

if (pri[p] == true)
{

for (int i = p * p; i <= num; i += p)
pri[i] = false;
}
}

for (int i = 2; i <= num; i++)
{ array[i] = array[i-1];

if (pri[i] == true)
array[i] = array[i]+1 ;
}
}

StringTokenizer st;

{
}

String next()
{
while (st == null || !st.hasMoreElements()) {
try {
}
catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt() { return Integer.parseInt(next()); }

long nextLong() { return Long.parseLong(next()); }

double nextDouble()
{
return Double.parseDouble(next());
}

String nextLine()
{
String str = "";
try {
}
catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
public static void main (String[] args) {
PrintWriter out = new PrintWriter(System.out);
int t ;
array = 0;
array = 0 ;

t =sol.nextInt();

primeGame(1000001);

while(t-- > 0)
{
int one = sol.nextInt();
int two = sol.nextInt();
if(array[one] <= two){
out.println("Chef");
}else{
out.println("Divyam");
}

}
out.flush();
out.close();

}
public static int sum(int n)
{
int res = 1;
return res;
}
public static int factorial(int n)
{

return n-1;

}
}```

Program Python:

```lst = [0,0]
def SieveOfEratosthenes(n):
prime = [True for i in range(n+1)]
p = 2
while (p * p <= n):
if (prime[p] == True):
for i in range(p * p, n+1, p):
prime[i] = False
p += 1
count = 0
for p in range(2, n+1):
if prime[p]:
count += 1
lst.append(count)
else:
lst.append(count)
SieveOfEratosthenes(1000001)
t = int(input())
from sys import stdin, stdout
for _ in range(t):